Heap sort

L'heap sort è un selection sort con un modo migliore di trovare il valore più grande. Tiene i valori non ordinati in un heap, un albero memorizzato dentro la lista stessa, in cui il valore più grande è sempre in cima. Toglierlo e riparare l'heap richiede circa log n passi invece di una scansione completa.

Un heap disegnato come albero binario sopra gli stessi valori come barre, con il valore più grande nella radice che viene scambiato con la fine della lista
Un heap disegnato come albero binario sopra gli stessi valori come barre, con il valore più grande nella radice che viene scambiato con la fine della lista

Un albero dentro una lista

Un heap binario è un albero che non ha bisogno di puntatori. La posizione 0 è la radice, e i figli della posizione i sono le posizioni 2i + 1 e 2i + 2: le posizioni 1 e 2 sono quindi i figli della radice, le posizioni da 3 a 6 il livello successivo, e così via. Ogni livello è pieno tranne l'ultimo, che si riempie da sinistra. In un max-heap ogni genitore è grande almeno quanto i suoi figli, quindi il valore più grande è sempre nella radice.

Far scendere un valore

Un'unica operazione fa tutto il lavoro. Per far scendere un valore, confrontalo con i suoi figli. Se il figlio più grande è più grande del valore, si scambiano, e il valore viene confrontato con i suoi nuovi figli. Si ferma quando nessun figlio è più grande o quando arriva in fondo. Poiché l'albero ha solo circa log₂ n livelli, una discesa richiede al massimo circa 2 log₂ n confronti.

Prima l'heap, poi l'ordinamento

Per costruire l'heap, fai scendere ogni genitore, dall'ultimo fino alla radice. Ogni sottoalbero è già un heap prima che il suo genitore ci scenda dentro. Poi ordina: scambia la radice, il valore più grande, con l'ultimo valore dell'heap. Quel valore è ora al suo posto definitivo. L'heap è più corto di uno, e il valore finito nella radice scende per ripararlo. Ripeti finché resta un solo valore.

Un esempio

Prendi 5, 1, 4, 2, 8. Costruendo l'heap, 1 scende sotto 8, poi 5 scende sotto 8, e si ottiene 8, 5, 4, 2, 1. Ora 8 va in fondo; 1 arriva nella radice e scende oltre 5 e 2: 5, 2, 4, 1 | 8. Poi 5 va in fondo e 1 scende oltre 4: 4, 2, 1 | 5, 8. Altri due giri completano la lista: 1, 2, 4, 5, 8, dopo 12 confronti e 10 scambi.

Pregi e difetti

L'heap sort richiede un tempo proporzionale a n log n anche nel caso peggiore, e non richiede memoria aggiuntiva. Il quicksort può rallentare fino a n² e il merge sort richiede un buffer lungo quanto la lista, quindi l'heap sort è la soluzione di riserva sicura: l'introsort, usato dalla libreria standard del C++, passa all'heap sort quando le partizioni del quicksort vanno male. Sui computer reali di solito è più lento di entrambi, perché salta tra posizioni lontane della lista, e non è stabile. J. W. J. Williams pubblicò l'heap sort, insieme all'heap binario, nel 1964.

Esploralo

Apri l'app e premi Passo. L'albero sopra le barre mostra l'heap: il valore che scende ha un colore tutto suo, il figlio con cui viene confrontato è evidenziato, e ogni scambio si vede sia nell'albero sia nelle barre. Quando l'heap è costruito, guarda la radice passare in fondo, diventare verde e uscire dall'albero.

Domande frequenti

Qual è la complessità temporale dell'heap sort?

O(n log n) nel caso migliore, medio e peggiore. Costruire l'heap richiede O(n), e ciascuna delle n − 1 estrazioni richiede O(log n). Ordina in loco con O(1) di memoria aggiuntiva.

Che differenza c'è tra heap sort e selection sort?

Entrambi prendono più volte il valore più grande (o più piccolo) rimasto. Il selection sort lo trova scandendo tutta la parte non ordinata, n confronti ogni volta. L'heap sort tiene la parte non ordinata in un heap, dove il valore più grande è già in cima, e riparare l'heap costa solo circa log n confronti.

A cosa serve un heap oltre all'ordinamento?

Alle code di priorità: un heap dà subito l'elemento più grande (o più piccolo) e permette di aggiungere o togliere elementi in circa log n passi. Gli scheduler, l'algoritmo dei cammini minimi di Dijkstra e le simulazioni a eventi lo usano tutti.

L'heap sort è stabile?

No. Scambiare la radice con la fine sposta i valori su lunghe distanze, quindi valori uguali possono cambiare il loro ordine.

Pronto a provarlo?

Apri PictorX nel tuo browser: nessuna installazione, nessuna carta di credito richiesta per iniziare.

Prova l'heap sort