En aquest article, parlarem de l'algoritme Heapsort. Heap sort processa els elements creant el min-heap o max-heap utilitzant els elements de la matriu donada. Min-heap o max-heap representa l'ordenació de la matriu en què l'element arrel representa l'element mínim o màxim de la matriu.
L'ordenació de pila bàsicament realitza de forma recursiva dues operacions principals:
- Construeix un munt H, utilitzant els elements de la matriu.
- Suprimiu repetidament l'element arrel de la pila formada a 1stfase.
Abans de saber més sobre l'ordenació de l'emmagatzematge de pila, primer veiem una breu descripció Munt.
Què és un munt?
Un munt és un arbre binari complet, i l'arbre binari és un arbre en què el node pot tenir el màxim de dos fills. Un arbre binari complet és un arbre binari en què tots els nivells excepte l'últim nivell, és a dir, el node fulla, s'han d'omplir completament i tots els nodes s'han de justificar a l'esquerra.
Què és l'ordenació de pila?
Heapsort és un algorisme d'ordenació popular i eficient. El concepte d'ordenació de pila consisteix a eliminar els elements un per un de la part de pila de la llista i, a continuació, inserir-los a la part ordenada de la llista.
Heapsort és l'algorisme d'ordenació in situ.
Rajinikanth
Ara, vegem l'algorisme d'ordenació de pila.
Algorisme
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
Funcionament de l'algoritme d'ordenació de pila
Ara, vegem el funcionament de l'algoritme Heapsort.
En l'ordenació de pila, bàsicament, hi ha dues fases implicades en l'ordenació d'elements. Mitjançant l'ús de l'algorisme d'ordenació de pila, són els següents:
- El primer pas inclou la creació d'un munt ajustant els elements de la matriu.
- Després de la creació de l'emmagatzematge munt, ara traieu l'element arrel de l'emmagatzematge muntatge repetidament desplaçant-lo al final de la matriu i, a continuació, emmagatzemeu l'estructura de l'muntatge amb els elements restants.
Ara vegem el funcionament de l'ordenació de pila en detall utilitzant un exemple. Per entendre-ho més clarament, agafem una matriu no ordenada i intentem ordenar-la mitjançant l'ordenació de pila. Farà l'explicació més clara i fàcil.
Primer, hem de construir un munt a partir de la matriu donada i convertir-lo en un munt màxim.
Després de convertir el munt donat al munt màxim, els elements de la matriu són -
A continuació, hem d'esborrar l'element arrel (89) del munt màxim. Per eliminar aquest node, hem d'intercanviar-lo amb l'últim node, és a dir. (11). Després d'eliminar l'element arrel, hem de tornar-lo a acumular per convertir-lo en un munt màxim.
Després d'intercanviar l'element de la matriu 89 amb 11, i convertint el munt en munt màxim, els elements de la matriu són -
En el següent pas, de nou, hem d'esborrar l'element arrel (81) del munt màxim. Per eliminar aquest node, hem d'intercanviar-lo amb l'últim node, és a dir. (54). Després d'eliminar l'element arrel, hem de tornar-lo a acumular per convertir-lo en un munt màxim.
Després d'intercanviar l'element de la matriu 81 amb 54 i convertint el munt en munt màxim, els elements de la matriu són -
En el següent pas, hem d'eliminar l'element arrel (76) des del munt màxim de nou. Per eliminar aquest node, hem d'intercanviar-lo amb l'últim node, és a dir. (9). Després d'eliminar l'element arrel, hem de tornar-lo a acumular per convertir-lo en un munt màxim.
Després d'intercanviar l'element de la matriu 76 amb 9 i convertint el munt en munt màxim, els elements de la matriu són -
En el següent pas, de nou hem d'esborrar l'element arrel (54) del munt màxim. Per eliminar aquest node, hem d'intercanviar-lo amb l'últim node, és a dir. (14). Després d'eliminar l'element arrel, hem de tornar-lo a acumular per convertir-lo en un munt màxim.
Després d'intercanviar l'element de la matriu 54 amb 14 i convertint el munt en munt màxim, els elements de la matriu són -
En el següent pas, de nou hem d'esborrar l'element arrel (22) del munt màxim. Per eliminar aquest node, hem d'intercanviar-lo amb l'últim node, és a dir. (11). Després d'eliminar l'element arrel, hem de tornar-lo a acumular per convertir-lo en un munt màxim.
Després d'intercanviar l'element de la matriu 22 amb 11 i convertint el munt en munt màxim, els elements de la matriu són -
En el següent pas, de nou hem d'esborrar l'element arrel (14) del munt màxim. Per eliminar aquest node, hem d'intercanviar-lo amb l'últim node, és a dir. (9). Després d'eliminar l'element arrel, hem de tornar-lo a acumular per convertir-lo en un munt màxim.
Exemples de codi de mostra de javascript
Després d'intercanviar l'element de la matriu 14 amb 9 i convertint el munt en munt màxim, els elements de la matriu són -
En el següent pas, de nou hem d'esborrar l'element arrel (11) del munt màxim. Per eliminar aquest node, hem d'intercanviar-lo amb l'últim node, és a dir. (9). Després d'eliminar l'element arrel, hem de tornar-lo a acumular per convertir-lo en un munt màxim.
Després d'intercanviar l'element de la matriu 11 amb 9, els elements de la matriu són -
Ara, al munt només li queda un element. Després de suprimir-lo, l'emmagatzematge dinàmic estarà buit.
Després de completar l'ordenació, els elements de la matriu són -
Ara, la matriu està completament ordenada.
Complexitat d'ordenació de pila
Ara, vegem la complexitat temporal de l'ordenació Heap en el millor dels casos, el cas mitjà i el pitjor dels casos. També veurem la complexitat espacial de Heapsort.
1. Complexitat temporal
| Caixa | Complexitat temporal |
|---|---|
| Millor cas | O(n registre) |
| Cas mitjà | O(n log n) |
| Pitjor dels casos | O(n log n) |
La complexitat temporal de l'ordenació de pila és O(n registre) en els tres casos (millor, mitjà i pitjor). L'alçada d'un arbre binari complet amb n elements és calma.
2. Complexitat espacial
| Complexitat espacial | O(1) |
| Estable | N0 |
- La complexitat espacial de l'ordenació Heap és O(1).
Implementació de Heapsort
Ara, anem a veure els programes d'ordenació Heap en diferents llenguatges de programació.
Programa: Escriu un programa per implementar l'ordenació de pila en llenguatge 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;>