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 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