Dans cet article, nous discuterons de l’algorithme Heapsort. Le tri par tas traite les éléments en créant le tas min ou le tas max en utilisant les éléments du tableau donné. Min-heap ou max-heap représente l'ordre du tableau dans lequel l'élément racine représente l'élément minimum ou maximum du tableau.
Le tri par tas effectue essentiellement de manière récursive deux opérations principales :
- Construisez un tas H, en utilisant les éléments du tableau.
- Supprimez à plusieurs reprises l'élément racine du tas formé en 1Stphase.
Avant d'en savoir plus sur le tri par tas, voyons d'abord une brève description de Tas.
Qu'est-ce qu'un tas ?
Un tas est un arbre binaire complet, et l'arbre binaire est un arbre dans lequel le nœud peut avoir au maximum deux enfants. Un arbre binaire complet est un arbre binaire dans lequel tous les niveaux sauf le dernier niveau, c'est-à-dire le nœud feuille, doivent être complètement remplis et tous les nœuds doivent être justifiés à gauche.
Qu’est-ce que le tri par tas ?
Heapsort est un algorithme de tri populaire et efficace. Le concept du tri par tas consiste à éliminer les éléments un par un de la partie tas de la liste, puis à les insérer dans la partie triée de la liste.
Heapsort est l'algorithme de tri sur place.
langage groovy
Voyons maintenant l'algorithme de tri par tas.
Algorithme
HeapSort(arr) BuildMaxHeap(arr) for i = length(arr) to 2 swap arr[1] with arr[i] heap_size[arr] = heap_size[arr] ? 1 MaxHeapify(arr,1) End
BuildMaxHeap(arr)
BuildMaxHeap(arr) heap_size(arr) = length(arr) for i = length(arr)/2 to 1 MaxHeapify(arr,i) End
MaxHeapify(arr,i)
MaxHeapify(arr,i) L = left(i) R = right(i) if L ? heap_size[arr] and arr[L] > arr[i] largest = L else largest = i if R ? heap_size[arr] and arr[R] > arr[largest] largest = R if largest != i swap arr[i] with arr[largest] MaxHeapify(arr,largest) End
Fonctionnement de l'algorithme de tri en tas
Voyons maintenant le fonctionnement de l'algorithme Heapsort.
Dans le tri par tas, le tri des éléments comporte essentiellement deux phases. En utilisant l'algorithme de tri par tas, ils sont les suivants :
- La première étape comprend la création d'un tas en ajustant les éléments du tableau.
- Après la création du tas, supprimez maintenant l'élément racine du tas à plusieurs reprises en le déplaçant vers la fin du tableau, puis stockez la structure du tas avec les éléments restants.
Voyons maintenant le fonctionnement du tri par tas en détail à l'aide d'un exemple. Pour le comprendre plus clairement, prenons un tableau non trié et essayons de le trier en utilisant le tri par tas. Cela rendra l’explication plus claire et plus facile.
Tout d’abord, nous devons construire un tas à partir du tableau donné et le convertir en tas maximum.
Après avoir converti le tas donné en tas maximum, les éléments du tableau sont -
Ensuite, nous devons supprimer l'élément racine (89) du tas maximum. Pour supprimer ce nœud, nous devons l'échanger avec le dernier nœud, c'est-à-dire (onze). Après avoir supprimé l'élément racine, nous devons à nouveau le compresser pour le convertir en tas maximum.
Après avoir échangé l'élément du tableau 89 avec onze, et en convertissant le tas en max-heap, les éléments du tableau sont -
À l'étape suivante, nous devons encore une fois supprimer l'élément racine (81) du tas maximum. Pour supprimer ce nœud, nous devons l'échanger avec le dernier nœud, c'est-à-dire (54). Après avoir supprimé l'élément racine, nous devons à nouveau le compresser pour le convertir en tas maximum.
Après avoir échangé l'élément du tableau 81 avec 54 et en convertissant le tas en max-heap, les éléments du tableau sont -
À l'étape suivante, nous devons supprimer l'élément racine (76) du tas maximum à nouveau. Pour supprimer ce nœud, nous devons l'échanger avec le dernier nœud, c'est-à-dire (9). Après avoir supprimé l'élément racine, nous devons à nouveau le compresser pour le convertir en tas maximum.
Après avoir échangé l'élément du tableau 76 avec 9 et en convertissant le tas en max-heap, les éléments du tableau sont -
À l'étape suivante, nous devons à nouveau supprimer l'élément racine (54) du tas maximum. Pour supprimer ce nœud, nous devons l'échanger avec le dernier nœud, c'est-à-dire (14). Après avoir supprimé l'élément racine, nous devons à nouveau le compresser pour le convertir en tas maximum.
Après avoir échangé l'élément du tableau 54 avec 14 et en convertissant le tas en max-heap, les éléments du tableau sont -
À l'étape suivante, nous devons à nouveau supprimer l'élément racine (22) du tas maximum. Pour supprimer ce nœud, nous devons l'échanger avec le dernier nœud, c'est-à-dire (onze). Après avoir supprimé l'élément racine, nous devons à nouveau le compresser pour le convertir en tas maximum.
Après avoir échangé l'élément du tableau 22 avec onze et en convertissant le tas en max-heap, les éléments du tableau sont -
mon flixeur
À l'étape suivante, nous devons à nouveau supprimer l'élément racine (14) du tas maximum. Pour supprimer ce nœud, nous devons l'échanger avec le dernier nœud, c'est-à-dire (9). Après avoir supprimé l'élément racine, nous devons à nouveau le compresser pour le convertir en tas maximum.
Après avoir échangé l'élément du tableau 14 avec 9 et en convertissant le tas en max-heap, les éléments du tableau sont -
À l'étape suivante, nous devons à nouveau supprimer l'élément racine (onze) du tas maximum. Pour supprimer ce nœud, nous devons l'échanger avec le dernier nœud, c'est-à-dire (9). Après avoir supprimé l'élément racine, nous devons à nouveau le compresser pour le convertir en tas maximum.
Après avoir échangé l'élément du tableau onze avec 9, les éléments du tableau sont -
Maintenant, le tas n’a plus qu’un seul élément. Après l'avoir supprimé, le tas sera vide.
Une fois le tri terminé, les éléments du tableau sont -
Maintenant, le tableau est complètement trié.
Complexité du tri en tas
Voyons maintenant la complexité temporelle du tri par tas dans le meilleur des cas, le cas moyen et le pire des cas. Nous verrons également la complexité spatiale de Heapsort.
1. Complexité temporelle
| Cas | Complexité temporelle |
|---|---|
| Meilleur cas | O (n journal) |
| Cas moyen | O (n journal n) |
| Pire cas | O (n journal n) |
La complexité temporelle du tri par tas est O (n journal) dans les trois cas (meilleur des cas, cas moyen et pire des cas). La hauteur d'un arbre binaire complet comportant n éléments est calme.
2. Complexité spatiale
| Complexité spatiale | O(1) |
| Écurie | N0 |
- La complexité spatiale du tri Heap est O(1).
Implémentation de Heapsort
Voyons maintenant les programmes de tri Heap dans différents langages de programmation.
Programme: Écrivez un programme pour implémenter le tri par tas en langage C.
#include /* function to heapify a subtree. Here 'i' is the index of root node in array a[], and 'n' is the size of heap. */ void heapify(int a[], int n, int i) { int largest = i; // Initialize largest as root int left = 2 * i + 1; // left child int right = 2 * i + 2; // right child // If left child is larger than root if (left a[largest]) largest = left; // If right child is larger than root if (right a[largest]) largest = right; // If root is not largest if (largest != i) { // swap a[i] with a[largest] int temp = a[i]; a[i] = a[largest]; a[largest] = temp; heapify(a, n, largest); } } /*Function to implement the heap sort*/ void heapSort(int a[], int n) { for (int i = n / 2 - 1; i >= 0; i--) heapify(a, n, i); // One by one extract an element from heap for (int i = n - 1; i >= 0; i--) { /* Move current root element to end*/ // swap a[0] with a[i] int temp = a[0]; a[0] = a[i]; a[i] = temp; heapify(a, i, 0); } } /* function to print the array elements */ void printArr(int arr[], int n) { for (int i = 0; i <n; ++i) { printf('%d', arr[i]); printf(' '); } int main() a[]="{48," 10, 23, 43, 28, 26, 1}; n="sizeof(a)" sizeof(a[0]); printf('before sorting array elements are -
'); printarr(a, n); heapsort(a, printf('
after return 0; < pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/50/heap-sort-algorithm-20.webp" alt="Heap Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement heap sort in C++.</p> <pre> #include using namespace std; /* function to heapify a subtree. Here 'i' is the index of root node in array a[], and 'n' is the size of heap. */ void heapify(int a[], int n, int i) { int largest = i; // Initialize largest as root int left = 2 * i + 1; // left child int right = 2 * i + 2; // right child // If left child is larger than root if (left a[largest]) largest = left; // If right child is larger than root if (right a[largest]) largest = right; // If root is not largest if (largest != i) { // swap a[i] with a[largest] int temp = a[i]; a[i] = a[largest]; a[largest] = temp; heapify(a, n, largest); } } /*Function to implement the heap sort*/ void heapSort(int a[], int n) { for (int i = n / 2 - 1; i >= 0; i--) heapify(a, n, i); // One by one extract an element from heap for (int i = n - 1; i >= 0; i--) { /* Move current root element to end*/ // swap a[0] with a[i] int temp = a[0]; a[0] = a[i]; a[i] = temp; heapify(a, i, 0); } } /* function to print the array elements */ void printArr(int a[], int n) { for (int i = 0; i <n; ++i) { cout< <a[i]<<' '; } int main() a[]="{47," 9, 22, 42, 27, 25, 0}; n="sizeof(a)" sizeof(a[0]); cout<<'before sorting array elements are -
'; printarr(a, n); heapsort(a, cout<<'
after return 0; < pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/50/heap-sort-algorithm-21.webp" alt="Heap Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement heap sort in C#.</p> <pre> using System; class HeapSort { /* function to heapify a subtree. Here 'i' is the index of root node in array a[], and 'n' is the size of heap. */ static void heapify(int[] a, int n, int i) { int largest = i; // Initialize largest as root int left = 2 * i + 1; // left child int right = 2 * i + 2; // right child // If left child is larger than root if (left a[largest]) largest = left; // If right child is larger than root if (right a[largest]) largest = right; // If root is not largest if (largest != i) { // swap a[i] with a[largest] int temp = a[i]; a[i] = a[largest]; a[largest] = temp; heapify(a, n, largest); } } /*Function to implement the heap sort*/ static void heapSort(int[] a, int n) { for (int i = n / 2 - 1; i >= 0; i--) heapify(a, n, i); // One by one extract an element from heap for (int i = n - 1; i >= 0; i--) { /* Move current root element to end*/ // swap a[0] with a[i] int temp = a[0]; a[0] = a[i]; a[i] = temp; heapify(a, i, 0); } } /* function to print the array elements */ static void printArr(int[] a, int n) { for (int i = 0; i <n; ++i) console.write(a[i] + ' '); } static void main() { int[] a="{46," 8, 21, 41, 26, 24, -1}; int n="a.Length;" console.write('before sorting array elements are -
'); printarr(a, n); heapsort(a, console.write('
after < pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/50/heap-sort-algorithm-22.webp" alt="Heap Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement heap sort in Java.</p> <pre> class HeapSort { /* function to heapify a subtree. Here 'i' is the index of root node in array a[], and 'n' is the size of heap. */ static void heapify(int a[], int n, int i) { int largest = i; // Initialize largest as root int left = 2 * i + 1; // left child int right = 2 * i + 2; // right child // If left child is larger than root if (left a[largest]) largest = left; // If right child is larger than root if (right a[largest]) largest = right; // If root is not largest if (largest != i) { // swap a[i] with a[largest] int temp = a[i]; a[i] = a[largest]; a[largest] = temp; heapify(a, n, largest); } } /*Function to implement the heap sort*/ static void heapSort(int a[], int n) { for (int i = n / 2 - 1; i >= 0; i--) heapify(a, n, i); // One by one extract an element from heap for (int i = n - 1; i >= 0; i--) { /* Move current root element to end*/ // swap a[0] with a[i] int temp = a[0]; a[0] = a[i]; a[i] = temp; heapify(a, i, 0); } } /* function to print the array elements */ static void printArr(int a[], int n) { for (int i = 0; i <n; ++i) system.out.print(a[i] + ' '); } public static void main(string args[]) { int a[]="{45," 7, 20, 40, 25, 23, -2}; n="a.length;" system.out.print('before sorting array elements are -
'); printarr(a, n); heapsort(a, system.out.print('
after < pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/50/heap-sort-algorithm-23.webp" alt="Heap Sort Algorithm"> <p>So, that's all about the article. Hope the article will be helpful and informative to you.</p> <hr></n;></pre></n;></pre></n;></pre></n;>