In questo tutorial imparerai come funziona l'algoritmo di ordinamento dell'heap. Inoltre, troverai esempi funzionanti di ordinamento di heap in C, C ++, Java e Python.
Heap Sort è un algoritmo di ordinamento popolare ed efficiente nella programmazione di computer. Imparare a scrivere l'algoritmo di ordinamento dell'heap richiede la conoscenza di due tipi di strutture dati: array e alberi.
L'insieme iniziale di numeri che vogliamo ordinare è memorizzato in un array, ad esempio (10, 3, 76, 34, 23, 32)e dopo l'ordinamento otteniamo un array ordinato(3,10,23,32,34,76)
L'ordinamento dell'heap funziona visualizzando gli elementi dell'array come un tipo speciale di albero binario completo chiamato heap.
Come prerequisito, è necessario conoscere un albero binario completo e una struttura dati dell'heap.
Relazione tra gli indici di array e gli elementi dell'albero
Un albero binario completo ha una proprietà interessante che possiamo usare per trovare i figli e i genitori di qualsiasi nodo.
Se l'indice di qualsiasi elemento nell'array è i, l'elemento nell'indice 2i+1diventerà il figlio sinistro e l'elemento 2i+2nell'indice diventerà il figlio destro. Inoltre, il genitore di qualsiasi elemento all'indice i è dato dal limite inferiore di (i-1)/2.
Relazione tra array e indici di heap
Proviamolo
Figlio sinistro di 1 (indice 0) = elemento in (2 * 0 + 1) indice = elemento in 1 indice = 12 Figlio destro di 1 = elemento in (2 * 0 + 2) indice = elemento in 2 indice = 9 Allo stesso modo, Figlio a sinistra di 12 (indice 1) = elemento in (2 * 1 + 1) indice = elemento in 3 indice = 5 Figlio a destra di 12 = elemento in (2 * 1 + 2) indice = elemento in 4 indice = 6
Confermiamo anche che le regole valgono per trovare il genitore di qualsiasi nodo
Genitore di 9 (posizione 2) = (2-1) / 2 = ½ = 0,5 ~ 0 indice = 1 Genitore di 12 (posizione 1) = (1-1) / 2 = 0 indice = 1
Comprendere questa mappatura degli indici degli array alle posizioni degli alberi è fondamentale per comprendere come funziona la struttura dei dati dell'heap e come viene utilizzata per implementare l'ordinamento dell'heap.
Che cos'è la struttura dei dati dell'heap?
Heap è una speciale struttura dati basata su albero. Si dice che un albero binario segua una struttura dati heap se
- è un albero binario completo
- Tutti i nodi dell'albero seguono la proprietà di essere maggiori dei loro figli, cioè l'elemento più grande è alla radice ed entrambi i suoi figli e più piccoli della radice e così via. Un tale heap è chiamato max-heap. Se invece tutti i nodi sono più piccoli dei loro figli, si parla di min-heap
Il seguente diagramma di esempio mostra Max-Heap e Min-Heap.
Heap massimo e Heap minimo
Per saperne di più, visita la struttura dei dati dell'heap.
Come "heapify" un albero
Partendo da un albero binario completo, possiamo modificarlo per diventare un Max-Heap eseguendo una funzione chiamata heapify su tutti gli elementi non foglia dell'heap.
Poiché heapify utilizza la ricorsione, può essere difficile da comprendere. Quindi pensiamo prima a come accumuleresti un albero con solo tre elementi.
heapify(array) Root = array(0) Largest = largest( array(0) , array (2*0 + 1). array(2*0+2)) if(Root != Largest) Swap(Root, Largest) 
Heapify casi di base
L'esempio sopra mostra due scenari: uno in cui la radice è l'elemento più grande e non è necessario fare nulla. E un altro in cui la radice aveva un elemento più grande da bambino e dovevamo scambiare per mantenere la proprietà max-heap.
Se hai già lavorato con algoritmi ricorsivi, probabilmente hai identificato che questo deve essere il caso di base.
Ora pensiamo a un altro scenario in cui è presente più di un livello.
Come heapify l'elemento root quando i suoi sottoalberi sono già max heap
L'elemento superiore non è un max-heap ma tutti i sottoalberi sono max-heap.
Per mantenere la proprietà max-heap per l'intero albero, dovremo continuare a spingere 2 verso il basso fino a raggiungere la sua posizione corretta.
Come heapify l'elemento radice quando i suoi sottoalberi sono max-heap
Pertanto, per mantenere la proprietà max-heap in un albero in cui entrambi i sottoalberi sono max-heap, è necessario eseguire ripetutamente heapify sull'elemento radice finché non è più grande dei suoi figli o diventa un nodo foglia.
Possiamo combinare entrambe queste condizioni in una funzione heapify come
void heapify(int arr(), int n, int i) ( // Find largest among root, left child and right child int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; if (left arr(largest)) largest = left; if (right arr(largest)) largest = right; // Swap and continue heapifying if root is not largest if (largest != i) ( swap(&arr(i), &arr(largest)); heapify(arr, n, largest); ) )
Questa funzione funziona sia per il caso base che per un albero di qualsiasi dimensione. Possiamo quindi spostare l'elemento radice nella posizione corretta per mantenere lo stato max-heap per qualsiasi dimensione dell'albero fintanto che i sottoalberi sono max-heap.
Crea max-heap
Per costruire un max-heap da qualsiasi albero, possiamo quindi iniziare a riempire ogni sottoalbero dal basso verso l'alto e finire con un max-heap dopo che la funzione è stata applicata a tutti gli elementi incluso l'elemento root.
Nel caso di un albero completo, il primo indice di un nodo non foglia è dato da n/2 - 1. Tutti gli altri nodi successivi sono nodi foglia e quindi non devono essere accumulati.
Quindi, possiamo creare un heap massimo come
// Build heap (rearrange array) for (int i = n / 2 - 1; i>= 0; i--) heapify(arr, n, i); 
Creare un array e calcolare i 
Passaggi per creare l'heap massimo per l'ordinamento dell'heap 
Passaggi per creare l'heap massimo per l'ordinamento dell'heap 
Passaggi per creare l'heap massimo per l'ordinamento dell'heap
Come mostrato nel diagramma sopra, iniziamo accumulando gli alberi più piccoli più bassi e gradualmente ci spostiamo verso l'alto fino a raggiungere l'elemento radice.
Se hai capito tutto fino a qui, congratulazioni, sei sulla buona strada per padroneggiare l'ordinamento Heap.
Come funziona l'ordinamento dell'heap?
- Poiché l'albero soddisfa la proprietà Max-Heap, l'elemento più grande viene archiviato nel nodo radice.
- Scambia: rimuove l'elemento radice e mettilo alla fine dell'array (n-esima posizione) Metti l'ultimo elemento dell'albero (mucchio) nel posto libero.
- Rimuovi: riduci le dimensioni dell'heap di 1.
- Heapify: heapify di nuovo l'elemento radice in modo da avere l'elemento più alto alla radice.
- Il processo viene ripetuto finché tutti gli elementi dell'elenco non vengono ordinati.
Swap, Remove e Heapify
Il codice seguente mostra l'operazione.
// Heap sort for (int i = n - 1; i>= 0; i--) ( swap(&arr(0), &arr(i)); // Heapify root element to get highest element at root again heapify(arr, i, 0); )
Esempi di Python, Java e C / C ++
Python Java C C ++ # Heap Sort in python def heapify(arr, n, i): # Find largest among root and children largest = i l = 2 * i + 1 r = 2 * i + 2 if l < n and arr(i) < arr(l): largest = l if r < n and arr(largest) < arr(r): largest = r # If root is not largest, swap with largest and continue heapifying if largest != i: arr(i), arr(largest) = arr(largest), arr(i) heapify(arr, n, largest) def heapSort(arr): n = len(arr) # Build max heap for i in range(n//2, -1, -1): heapify(arr, n, i) for i in range(n-1, 0, -1): # Swap arr(i), arr(0) = arr(0), arr(i) # Heapify root element heapify(arr, i, 0) arr = (1, 12, 9, 5, 6, 10) heapSort(arr) n = len(arr) print("Sorted array is") for i in range(n): print("%d " % arr(i), end='')
// Heap Sort in Java public class HeapSort ( public void sort(int arr()) ( int n = arr.length; // Build max heap for (int i = n / 2 - 1; i>= 0; i--) ( heapify(arr, n, i); ) // Heap sort for (int i = n - 1; i>= 0; i--) ( int temp = arr(0); arr(0) = arr(i); arr(i) = temp; // Heapify root element heapify(arr, i, 0); ) ) void heapify(int arr(), int n, int i) ( // Find largest among root, left child and right child int largest = i; int l = 2 * i + 1; int r = 2 * i + 2; if (l arr(largest)) largest = l; if (r arr(largest)) largest = r; // Swap and continue heapifying if root is not largest if (largest != i) ( int swap = arr(i); arr(i) = arr(largest); arr(largest) = swap; heapify(arr, n, largest); ) ) // Function to print an array static void printArray(int arr()) ( int n = arr.length; for (int i = 0; i < n; ++i) System.out.print(arr(i) + " "); System.out.println(); ) // Driver code public static void main(String args()) ( int arr() = ( 1, 12, 9, 5, 6, 10 ); HeapSort hs = new HeapSort(); hs.sort(arr); System.out.println("Sorted array is"); printArray(arr); ) )
// Heap Sort in C #include // Function to swap the the position of two elements void swap(int *a, int *b) ( int temp = *a; *a = *b; *b = temp; ) void heapify(int arr(), int n, int i) ( // Find largest among root, left child and right child int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; if (left arr(largest)) largest = left; if (right arr(largest)) largest = right; // Swap and continue heapifying if root is not largest if (largest != i) ( swap(&arr(i), &arr(largest)); heapify(arr, n, largest); ) ) // Main function to do heap sort void heapSort(int arr(), int n) ( // Build max heap for (int i = n / 2 - 1; i>= 0; i--) heapify(arr, n, i); // Heap sort for (int i = n - 1; i>= 0; i--) ( swap(&arr(0), &arr(i)); // Heapify root element to get highest element at root again heapify(arr, i, 0); ) ) // Print an array void printArray(int arr(), int n) ( for (int i = 0; i < n; ++i) printf("%d ", arr(i)); printf(""); ) // Driver code int main() ( int arr() = (1, 12, 9, 5, 6, 10); int n = sizeof(arr) / sizeof(arr(0)); heapSort(arr, n); printf("Sorted array is "); printArray(arr, n); )
// Heap Sort in C++ #include using namespace std; void heapify(int arr(), int n, int i) ( // Find largest among root, left child and right child int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; if (left arr(largest)) largest = left; if (right arr(largest)) largest = right; // Swap and continue heapifying if root is not largest if (largest != i) ( swap(arr(i), arr(largest)); heapify(arr, n, largest); ) ) // main function to do heap sort void heapSort(int arr(), int n) ( // Build max heap for (int i = n / 2 - 1; i>= 0; i--) heapify(arr, n, i); // Heap sort for (int i = n - 1; i>= 0; i--) ( swap(arr(0), arr(i)); // Heapify root element to get highest element at root again heapify(arr, i, 0); ) ) // Print an array void printArray(int arr(), int n) ( for (int i = 0; i < n; ++i) cout << arr(i) << " "; cout << ""; ) // Driver code int main() ( int arr() = (1, 12, 9, 5, 6, 10); int n = sizeof(arr) / sizeof(arr(0)); heapSort(arr, n); cout << "Sorted array is "; printArray(arr, n); )
Complessità di ordinamento mucchio
L'ordinamento heap presenta O(nlog n)complessità temporali per tutti i casi (caso migliore, caso medio e caso peggiore).
Cerchiamo di capire il motivo. L'altezza di un albero binario completo contenente n elementi èlog n
As we have seen earlier, to fully heapify an element whose subtrees are already max-heaps, we need to keep comparing the element with its left and right children and pushing it downwards until it reaches a point where both its children are smaller than it.
In the worst case scenario, we will need to move an element from the root to the leaf node making a multiple of log(n) comparisons and swaps.
During the build_max_heap stage, we do that for n/2 elements so the worst case complexity of the build_heap step is n/2*log n ~ nlog n.
During the sorting step, we exchange the root element with the last element and heapify the root element. For each element, this again takes log n worst time because we might have to bring the element all the way from the root to the leaf. Since we repeat this n times, the heap_sort step is also nlog n.
Also since the build_max_heap and heap_sort steps are executed one after another, the algorithmic complexity is not multiplied and it remains in the order of nlog n.
Also it performs sorting in O(1) space complexity. Compared with Quick Sort, it has a better worst case ( O(nlog n) ). Quick Sort has complexity O(n^2) for worst case. But in other cases, Quick Sort is fast. Introsort is an alternative to heapsort that combines quicksort and heapsort to retain advantages of both: worst case speed of heapsort and average speed of quicksort.
Heap Sort Applications
Systems concerned with security and embedded systems such as Linux Kernel use Heap Sort because of the O(n log n) upper bound on Heapsort's running time and constant O(1) upper bound on its auxiliary storage.
Sebbene Heap Sort abbia una O(n log n)complessità temporale anche nel caso peggiore, non ha più applicazioni (rispetto ad altri algoritmi di ordinamento come Quick Sort, Merge Sort). Tuttavia, la sua struttura dati sottostante, l'heap, può essere utilizzata in modo efficiente se si desidera estrarre il più piccolo (o il più grande) dall'elenco di elementi senza l'overhead di mantenere gli elementi rimanenti nell'ordine ordinato. Ad esempio, code prioritarie.
