La fase di estrazione esegue n−1 ripristini del heap, ciascuno fino a log n livelli: Θ(n log n) anche nel caso migliore standard.
Algoritmi di ordinamento · 4/7
Heapsort
Trasforma l’array in un max-heap e porta i massimi in fondo.
Tempo medioΘ(n log n)
MemoriaΘ(1)
StabileNo
In placeSì
Come funziona
Nel max-heap ogni genitore è almeno grande quanto i figli. La radice contiene il massimo: viene scambiata con la fine della parte attiva, poi si ripristina il heap.
Invariante: Dopo ogni estrazione, il suffisso è ordinato e definitivo; il prefisso è un max-heap.
Simulazione passo passo
Ogni barra rappresenta un elemento. I colori distinguono gli elementi confrontati, il pivot o la chiave, la parte già definitiva e l’area attiva.
Da 2 a 16 valori. Per questo simulatore sono ammessi valori da 0 a 999.
- Confronti
- 0
- Scritture
- 0
- Scambi
- 0
- Passaggio / livello
- 0
attivo
confronto
pivot / chiave
definitivo
Pseudocodice collegato alla simulazione
buildMaxHeap(A)for end ← n − 1 downto 1swap A[0], A[end]siftDown(A, 0, end)siftDown(A, root, end)child ← 2 · root + 1choose the larger childif child > root: swap and continue
La riga evidenziata corrisponde all’operazione descritta nel simulatore. I dettagli di gestione degli indici sono intenzionalmente semplificati.
Studio della complessità
Build-heap costa Θ(n); le estrazioni dominano con Θ(n log n).
L’altezza del heap è sempre Θ(log n), quindi il limite peggiore resta Θ(n log n).
Gli scambi avvengono nello stesso array e la versione iterativa usa Θ(1) spazio. Gli scambi a lunga distanza distruggono la stabilità.
Proprietà in breve
La stabilità riguarda l’ordine relativo degli elementi con chiave uguale.
La classificazione considera la versione dell’algoritmo mostrata in questa pagina.
Quando usarlo e che cosa evitare
Buona scelta quando…
Utile quando si vuole una garanzia Θ(n log n) con memoria ausiliaria costante; alla base anche delle code di priorità.
Errore comune
Costruire il heap con n inserimenti costa Θ(n log n); il build-heap bottom-up corretto costa Θ(n).