In questo articolo discuteremo dell'algoritmo Heapsort. L'ordinamento dell'heap elabora gli elementi creando il min-heap o il max-heap utilizzando gli elementi dell'array specificato. Min-heap o max-heap rappresenta l'ordinamento dell'array in cui l'elemento root rappresenta l'elemento minimo o massimo dell'array.
L'ordinamento dell'heap esegue fondamentalmente in modo ricorsivo due operazioni principali:
- Costruisci un heap H, usando gli elementi dell'array.
- Elimina ripetutamente l'elemento root dell'heap formato in 1stfase.
Prima di saperne di più sull'heap sort, vediamo prima una breve descrizione di Mucchio.
Cos'è un mucchio?
Un heap è un albero binario completo e l'albero binario è un albero in cui il nodo può avere al massimo due figli. Un albero binario completo è un albero binario in cui tutti i livelli tranne l'ultimo livello, cioè il nodo foglia, dovrebbero essere completamente riempiti e tutti i nodi dovrebbero essere giustificati a sinistra.
Cos'è l'ordinamento dell'heap?
Heapsort è un algoritmo di ordinamento popolare ed efficiente. Il concetto dell'ordinamento heap è quello di eliminare gli elementi uno per uno dalla parte heap dell'elenco e quindi inserirli nella parte ordinata dell'elenco.
Heapsort è l'algoritmo di ordinamento sul posto.
cos'è GB
Ora vediamo l'algoritmo dell'heap sort.
Algoritmo
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
Funzionamento dell'algoritmo di ordinamento Heap
Ora vediamo il funzionamento dell'algoritmo Heapsort.
Nell'heap sort, fondamentalmente, ci sono due fasi coinvolte nell'ordinamento degli elementi. Utilizzando l'algoritmo di ordinamento dell'heap, sono i seguenti:
- Il primo passaggio prevede la creazione di un heap modificando gli elementi dell'array.
- Dopo la creazione dell'heap, ora rimuovi ripetutamente l'elemento radice dell'heap spostandolo alla fine dell'array, quindi memorizza la struttura dell'heap con gli elementi rimanenti.
Ora vediamo in dettaglio il funzionamento dell'heap sort utilizzando un esempio. Per capirlo più chiaramente, prendiamo un array non ordinato e proviamo a ordinarlo utilizzando l'ordinamento heap. Renderà la spiegazione più chiara e semplice.
Per prima cosa dobbiamo costruire un heap dall'array dato e convertirlo nell'heap massimo.
Dopo aver convertito l'heap specificato nell'heap massimo, gli elementi dell'array sono:
Successivamente, dobbiamo eliminare l'elemento root (89) dall'heap massimo. Per eliminare questo nodo, dobbiamo scambiarlo con l'ultimo nodo, cioè (undici). Dopo aver eliminato l'elemento root, dobbiamo nuovamente heapificarlo per convertirlo in max heap.
Dopo aver scambiato l'elemento dell'array 89 con undici, e convertendo l'heap in max-heap, gli elementi dell'array sono:
Nel passaggio successivo, ancora una volta, dobbiamo eliminare l'elemento root (81) dall'heap massimo. Per eliminare questo nodo, dobbiamo scambiarlo con l'ultimo nodo, cioè (54). Dopo aver eliminato l'elemento root, dobbiamo nuovamente heapificarlo per convertirlo in max heap.
Dopo aver scambiato l'elemento dell'array 81 con 54 e convertendo l'heap in max-heap, gli elementi dell'array sono:
Nel passaggio successivo, dobbiamo eliminare l'elemento root (76) di nuovo dall'heap massimo. Per eliminare questo nodo, dobbiamo scambiarlo con l'ultimo nodo, cioè (9). Dopo aver eliminato l'elemento root, dobbiamo nuovamente heapificarlo per convertirlo in max heap.
Dopo aver scambiato l'elemento dell'array 76 con 9 e convertendo l'heap in max-heap, gli elementi dell'array sono:
Nel passaggio successivo, dobbiamo eliminare nuovamente l'elemento root (54) dall'heap massimo. Per eliminare questo nodo, dobbiamo scambiarlo con l'ultimo nodo, cioè (14). Dopo aver eliminato l'elemento root, dobbiamo nuovamente heapificarlo per convertirlo in max heap.
Dopo aver scambiato l'elemento dell'array 54 con 14 e convertendo l'heap in max-heap, gli elementi dell'array sono:
Nel passaggio successivo, dobbiamo eliminare nuovamente l'elemento root (22) dall'heap massimo. Per eliminare questo nodo, dobbiamo scambiarlo con l'ultimo nodo, cioè (undici). Dopo aver eliminato l'elemento root, dobbiamo nuovamente heapificarlo per convertirlo in max heap.
Dopo aver scambiato l'elemento dell'array 22 con undici e convertendo l'heap in max-heap, gli elementi dell'array sono:
Nel passaggio successivo, dobbiamo eliminare nuovamente l'elemento root (14) dall'heap massimo. Per eliminare questo nodo, dobbiamo scambiarlo con l'ultimo nodo, cioè (9). Dopo aver eliminato l'elemento root, dobbiamo nuovamente heapificarlo per convertirlo in max heap.
Dopo aver scambiato l'elemento dell'array 14 con 9 e convertendo l'heap in max-heap, gli elementi dell'array sono:
Nel passaggio successivo, dobbiamo eliminare nuovamente l'elemento root (undici) dall'heap massimo. Per eliminare questo nodo, dobbiamo scambiarlo con l'ultimo nodo, cioè (9). Dopo aver eliminato l'elemento root, dobbiamo nuovamente heapificarlo per convertirlo in max heap.
Dopo aver scambiato l'elemento dell'array undici con 9, gli elementi dell'array sono:
Ora, all'heap è rimasto un solo elemento. Dopo averlo eliminato, l'heap sarà vuoto.
Dopo il completamento dell'ordinamento, gli elementi dell'array sono:
Ora l'array è completamente ordinato.
jtextfield
Complessità dell'ordinamento dell'heap
Ora, vediamo la complessità temporale dell'ordinamento Heap nel caso migliore, nel caso medio e nel caso peggiore. Vedremo anche la complessità spaziale di Heapsort.
1. Complessità temporale
| Caso | Complessità temporale |
|---|---|
| Caso migliore | O(n registro) |
| Caso medio | O(n log n) |
| Caso peggiore | O(n log n) |
La complessità temporale dell'ordinamento dell'heap è O(n registro) in tutti e tre i casi (caso migliore, caso medio e caso peggiore). L'altezza di un albero binario completo di n elementi è calma.
2. Complessità spaziale
| Complessità spaziale | O(1) |
| Stabile | N0 |
- La complessità spaziale dell'ordinamento Heap è O(1).
Implementazione di Heapsort
Vediamo ora i programmi di Heap sort nei diversi linguaggi di programmazione.
Programma: Scrivere un programma per implementare l'heap sort in linguaggio 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;>