Heapify All The Things With Heap Sort
Qualcuno una volta mi ha detto che tutto ciò che è importante nell’informatica si riduce agli alberi. Letteralmente solo alberi. Possiamo usarli per costruire cose, analizzare cose e interpretare cose (sì, qui potrebbe esserci qualche prefigurazione, non preoccupatevi se non ha ancora senso per voi, perché presto lo avrà). E possiamo anche usarli per – avete indovinato! – ordinare le cose.
Ah, ordinare. Ne abbiamo fatto tanto nelle ultime settimane, ma ora siamo vicini alla fine delle nostre avventure di smistamento. Tuttavia, è impossibile e ingiusto parlare di ordinamento senza parlare di un tipo speciale di ordinamento che utilizza la più recente struttura di dati nella nostra cintura di strumenti per la struttura dei dati.
Di recente abbiamo imparato ad amare gli heap, un tipo speciale di albero binario che segue un rigido insieme di regole, e sono usati per implementare cose come code di priorità e lavori in background. Ma queste non sono le uniche cose per cui gli heap sono buoni. Si scopre che gli heap binari sono spesso utilizzati per nessun altro scopo che l’ordinamento efficiente. Molti programmi si basano sull’heap sort poiché è uno dei modi più efficienti per ordinare un array. E ora che sappiamo cos’è un heap, possiamo cercare di capire perché funziona così bene quando si tratta del problema dell’ordinamento!
Prima di tuffarci nell’heap sort, assicuriamoci di avere bene in mente gli heap. Potremmo ricordare che un heap non è altro che un albero binario con alcune regole aggiuntive che deve seguire: primo, deve sempre avere una struttura heap, dove tutti i livelli dell’albero binario sono riempiti, da sinistra a destra, e secondo, deve essere ordinato come max heap o min heap. Per gli scopi dell’heap sort, avremo a che fare esclusivamente con gli heap max, dove ogni nodo padre (inclusa la radice) è maggiore o uguale al valore dei suoi nodi figli.
Ok, andiamo a rispondere alla domanda del momento: come facciamo a ordinare usando gli heap? Bene, per rispondere a questa domanda, dobbiamo prima capire cos’è un algoritmo di heap sort!
Un algoritmo di heap sort è una tecnica di ordinamento che si basa su strutture dati binari heap. Poiché sappiamo che gli heap devono sempre seguire un ordine specifico, possiamo sfruttare questa proprietà e usarla per trovare l’elemento più grande, di valore massimo, e ordinare sequenzialmente gli elementi selezionando il nodo radice di un heap e aggiungendolo alla fine dell’array.
Sappiamo già che l’heap sort è un modo efficiente di ordinare un array non ordinato; ma cosa ha a che fare un array con un heap? E come facciamo ad ordinare un array usando un heap? Bene, ci sono tre passi chiave per come funziona in pratica. Li approfondiremo tra un momento, ma diamo prima un’occhiata ad alto livello a cosa sono questi tre passi.
- Per iniziare, abbiamo un array non ordinato. Il primo passo è prendere quell’array e trasformarlo in un heap; nel nostro caso, vogliamo trasformarlo in un max heap. Quindi, dobbiamo trasformare e costruire un max heap dai dati del nostro array non ordinato. Di solito, questo è incapsulato da una singola funzione, che potrebbe essere chiamata qualcosa come
buildMaxHeap. - Una volta che abbiamo i dati del nostro array in un formato max heap, possiamo essere sicuri che il valore più grande sia al nodo radice dell’heap. Ricordate che, anche se l’intero heap non sarà ordinato, se abbiamo costruito il nostro max heap correttamente e senza errori, ogni singolo nodo padre nel nostro heap avrà un valore più grande dei suoi figli. Quindi, sposteremo il valore più grande – situato nel nodo radice – alla fine dell’heap scambiandolo con l’ultimo elemento.
- Ora, l’elemento più grande dell’heap si trova nell’ultimo nodo, il che è fantastico. Sappiamo che è nella sua posizione ordinata, quindi può essere rimosso completamente dall’heap. Ma c’è ancora un altro passo: assicurarsi che il nuovo elemento del nodo radice sia nel posto giusto! È altamente improbabile che l’elemento che abbiamo scambiato nella posizione del nodo radice sia nella posizione giusta, quindi sposteremo l’elemento del nodo radice nella sua posizione corretta, usando una funzione che di solito si chiama qualcosa come
heapify.
E questo è praticamente tutto! L’algoritmo continua a ripetere questi passi fino a quando l’heap non si riduce a un solo nodo. A quel punto, sa che tutti gli elementi nell’array non ordinato sono nelle loro posizioni ordinate, e che l’ultimo nodo rimanente finirà per essere il primo elemento nell’array ordinato.
Ok, so che ho detto che questi sono gli unici tre passi dell’heap sort. Ma se questi tre passi vi sembrano confusi, non preoccupatevi; possono essere piuttosto complicati e difficili da capire finché non li vedete in azione. Infatti, penso che questo algoritmo abbia molto più senso con un esempio illustrato. Poiché gli heap sono un tipo di albero, aiuta visualizzarli, nello stesso modo in cui facciamo con gli alberi binari. Quindi facciamolo subito!
Hai mai guardato sotto il cofano dell’heap sort?
Ebbene, è il momento della mia parte preferita in assoluto dell’apprendimento dell’heap sort: disegnarlo! Urrà! Per capire cosa succede sotto il cofano dell’heap sort, lavoreremo con un piccolo set di dati non ordinato.
Partiamo con un array non ordinato con cinque elementi che sono super fuori ordine: .
Ricordate che, dato che stiamo lavorando con l’heap sort, avremo bisogno di trasformare l’array in un heap, per iniziare.
Nell’illustrazione mostrata qui, potete vedere che l’array è stato trasformato in un albero – non è ancora un heap perché non è ancora in nessun ordine max o min heap! Possiamo vedere che questo è il caso perché 3 non è l’elemento più grande o più piccolo, eppure, è il nodo radice al momento. Questo è solo un albero, con gli elementi dell’array direttamente tradotti in un formato di albero binario.
Ma, poiché abbiamo bisogno di trattare un max heap, dovremo trasformare la nostra struttura da un albero binario in un max heap. Notate come, nel max heap, i nodi genitori sono tutti più grandi dei loro figli. La settimana scorsa abbiamo imparato gli algoritmi che ci permettono di determinare i nodi figli dall’indice di un array; questa settimana li vediamo in azione. Questi algoritmi sono ciò che stiamo usando per trasformare questo array in un albero, e poi in un heap.
Ok, ora abbiamo un vero e proprio max heap. Grande! Ora per il lavoro effettivo di ordinamento.
Siccome sappiamo che l’elemento più grande è nel nodo radice, sappiamo che dovremo metterlo proprio alla fine dell’array, nell’ultimo posto disponibile dell’indice. Quindi, scambieremo il nodo radice con l’ultimo nodo. Una volta fatto questo scambio, il nostro ultimo nodo conterrà l’elemento più grande e di valore massimo.
Fico! Ora possiamo vedere che 19, l’elemento più grande, che prima era il nodo radice, è ora nell’ultima posizione dell’array. E, poiché è effettivamente “ordinato” rispetto al resto degli elementi, possiamo rimuoverlo completamente dall’heap.
Ora, la buona notizia è che abbiamo un nodo in meno nel nostro heap da ordinare! La cattiva notizia? Il nostro heap non è più un heap: sta violando totalmente la sua regola di ordine dell’heap, poiché non è un heap massimo. Notate che 1 è il nodo radice, ma non è sicuramente più grande dei suoi due nodi figli, 14 e 7. Quindi, dovremo spostarlo in basso al suo posto corretto nell’albero.
Implementiamo questo albero e rendiamolo di nuovo un max heap!
Fantastico! Nell’illustrazione qui sopra, possiamo vedere che abbiamo prima scambiato 1 e 14, e poi abbiamo scambiato 1 e 8. Ora siamo tornati a un vero e proprio max heap. Possiamo ripetere gli stessi passi che abbiamo fatto per ordinare l’elemento 19:
→ Prima scambieremo il primo e l’ultimo nodo.
→ Poi, heapificheremo l’albero finché non sarà di nuovo un max heap corretto.
Facciamo questo con il nostro nuovo nodo radice, l’elemento 14. Ecco come sarebbero i nostri prossimi due passi:
Rad! Abbiamo scambiato il primo e l’ultimo nodo, e poi abbiamo rimosso l’ultimo nodo, 14, poiché era nella sua posizione ordinata. L’unica cosa che dovevamo fare dopo era spostare il nodo radice nella sua posizione corretta, e heapificare l’elemento 3 fino a quando non fossimo tornati allo stato di max heap.
Continuavamo a fare questo per altre tre volte. Alla fine, saremmo rimasti con solo 1, l’ultimo nodo nell’heap. A questo punto, l’algoritmo di heap sort sarebbe finito, e sapremmo che 1 sarebbe il primo elemento dell’array, e sapremmo che l’array è finalmente ordinato.
Qui c’è una grande visualizzazione dell’intero processo che abbiamo appena attraversato. Notate come, con ogni ordinamento iterativo, il più grande elemento non ordinato finisce nel suo posto corretto nell’heap, e poi nell’array.
Heap sort: a cosa serve? Solo dopo aver illustrato l’heap sort ho capito da dove veniva la mia sensazione di déjà vu: l’heap sort era quasi esattamente come il selection sort! Forse vi ricorderete da prima nella serie che il selection sort è un algoritmo che ordina una lista di elementi non ordinati iterando attraverso una lista di elementi, trovando il più piccolo, e mettendolo da parte in una lista ordinata. Continua ad ordinare trovando il più piccolo elemento non ordinato, e aggiungendolo alla lista ordinata.
Non suona molto simile all’heap sort, ma solo invertito?
Si scopre che l’heap sort è molto simile al selection sort nella sua logica: entrambi gli algoritmi trovano l’elemento più piccolo o più grande, lo “selezionano”, e mettono quell’elemento nella sua posizione corretta nella lista ordinata.
Tuttavia, per quanto siano simili, l’heap sort è molto meglio del selection sort in un modo enorme: la sua performance! L’heap sort è fondamentalmente una versione super-migliorata del selection sort. Sì, trova l’elemento più grande in una collezione non ordinata e lo ordina in fondo alla lista – tuttavia, fa tutto questo lavoro molto più velocemente di quanto farebbe selection sort!
Ok, quindi quanto è più veloce heap sort? E perché è più veloce?
Beh, diamo un’occhiata al codice. Ci sono varie implementazioni di heap sort, e il codice qui sotto è adattato dall’implementazione JavaScript di Rosetta Code di heap sort. Vi ricorderete che l’heap sort ha due parti importanti: buildMaxHeap e heapify. Possiamo vederle in azione nella versione di heapSort qui sotto.
La funzione buildMaxHeap fa il lavoro di creare effettivamente il max heap. Notate che anche questa funzione chiama heapify, che fa il lavoro di spostare un elemento alla volta nella sua corretta posizione nell’heap.
La funzione heapify è piuttosto importante, quindi guardiamola. Notate che si basa sugli algoritmi per determinare il figlio sinistro e destro di un nodo, di cui abbiamo discusso la settimana scorsa quando abbiamo imparato gli heap.
E infine, ma non meno importante, la funzione swap, che abbiamo già visto in altri algoritmi di ordinamento, ma che vale la pena guardare velocemente per ricordarci cosa fa:
Ok, ora che abbiamo un po’ di contesto su come queste funzioni interagiscono e si invocano a vicenda, torniamo alla nostra domanda originale su come e perché l’heap sort è molto più efficiente del selection sort! Se guardiamo a fondo il codice, noteremo due cose: primo, dobbiamo costruire l’heap max una volta, passandogli tutti gli elementi dell’array; secondo, dobbiamo heapificare tutti gli elementi nell’heap ancora e ancora, con l’eccezione del primo elemento del nodo radice.
Queste due osservazioni sono in realtà la chiave della questione di come e perché l’heap sort sia così veloce. Chiamare buildMaxHeap richiede tempo O(n), poiché ogni singolo elemento deve essere aggiunto all’heap, e una maggiore quantità di elementi significa un heap più grande. Tuttavia, ricordate che abbiamo a che fare con un albero binario, e gli alberi binari sono di natura logaritmica. Quindi, anche se dobbiamo chiamare heapify ancora e ancora, invocare questa funzione è in realtà abbastanza veloce, dato che verrà eseguita in tempo logaritmico, o O(log n).
La combinazione di queste due complessità temporali è qualcosa che abbiamo già visto prima! Heap sort viene eseguito in tempo linearmente, o in notazione Big O, O(n log n). Quindi, anche se l’heap sort sembra molto simile al selection sort, è molto più veloce! Selection sort funziona in tempo quadratico, o O(n²), che è molto meno efficiente del tempo linearitmico.
Guardiamo velocemente gli altri modi in cui heap sort si confronta con altri algoritmi di ordinamento.
L’heap sort trasforma l’array che gli passa mentre ordina; a differenza di alcuni algoritmi di ordinamento, non crea una copia completamente separata dei dati in ingresso. Questo lo rende un algoritmo di ordinamento in-place. Heap sort non ha bisogno di memoria esterna, ed è un algoritmo di ordinamento interno. Viene eseguito iterativamente (e quindi non è ricorsivo), e confronta due elementi alla volta quando scambia e chiama la funzione heapify, rendendolo un algoritmo di ordinamento comparativo.
Tuttavia, a causa della natura degli heap e della funzione heapify, se ci sono elementi duplicati, non possiamo contare sul fatto che gli elementi mantengano il loro ordine! Quindi, l’heap sort è instabile; questo è uno dei principali fattori di differenziazione tra il merge sort e l’heap sort, che si basano entrambi su strutture ad albero per funzionare in modo efficiente. Tuttavia, il merge sort vince nella battaglia della stabilità, mentre l’heap sort fallisce in questa categoria.
Nonostante le loro differenze, il merge sort e l’heap sort possono essere d’accordo su una cosa: senza alberi binari, sarebbero entrambi persi!
Risorse
Ci sono alcuni appunti e lezioni davvero fantastici sull’heap sort, così come alcuni buoni tutorial video. Ho fatto un po’ di ricerche su Google in modo che non dobbiate farlo voi! Ecco alcuni ottimi posti per iniziare se sei interessato a saperne di più sull’heap sort.
- Introduzione agli algoritmi: Heap Sort, MIT
- Algoritmi: Heap Sort, Professor Ching-Chi Lin
- Heap sort, Growing with the Web
- Heap sort in 4 minutes, Michael Sambol
- Heap sort: Max heap, strohtennis
Leave a Reply