mastorna.it
EN

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.

Che cos’è un heap

Un heap binario è un albero binario completo che rispetta una relazione d’ordine locale. “Completo” significa che tutti i livelli sono pieni, tranne eventualmente l’ultimo, che viene riempito da sinistra verso destra. Questa forma garantisce altezza Θ(log n).

Proprietà del max-heap

Ogni nodo è maggiore o uguale ai propri figli. Di conseguenza il massimo dell’intero heap si trova sempre nella radice A[0]. Non è necessario che fratelli o sottoalberi diversi siano ordinati tra loro.

Rappresentazione nell’array

Non servono puntatori: con indici da zero, i figli di A[i] sono A[2i+1] e A[2i+2], mentre per i > 0 il padre di A[i] è A[⌊(i−1)/2⌋]. Gli indici oltre la lunghezza corrente dell’heap non appartengono all’albero.

Esempio

L’array [9, 7, 6, 4, 3, 1, 5, 2] rappresenta un max-heap: A[0]=9 domina 7 e 6; A[1]=7 domina 4 e 3; la stessa proprietà vale per ogni altro genitore.

Heap e BST non sono la stessa cosa. In un BST tutte le chiavi del sottoalbero sinistro sono minori del nodo e tutte quelle del sottoalbero destro sono maggiori; in un max-heap si confrontano soltanto genitore e figli. L’heap trova rapidamente il massimo, ma non permette una ricerca ordinata arbitraria.

Simulazione passo passo

La vista a barre mostra scambi e parte ordinata; la rappresentazione parallela collega ogni posizione dell’array al nodo corrispondente del max-heap.

Da 2 a 16 valori. Per questo simulatore sono ammessi valori da 0 a 999.

Max-heap: albero e array Figli di A[i]: A[2i+1] e A[2i+2] · verde: posizione ordinata

Confronti
0
Scritture
0
Scambi
0
Passaggio / livello
0
attivo confronto massimo estratto definitivo

Pseudocodice collegato alla simulazione

Heap sort

  1. heapSort(A)
  2. buildMaxHeap(A)
  3. for end ← length(A) − 1 downto 1
  4. swap A[0], A[end]
  5. siftDown(A, 0, end)

buildMaxHeap

  1. buildMaxHeap(A)
  2. for root ← ⌊length(A) / 2⌋ − 1 downto 0
  3. siftDown(A, root, length(A))

siftDown

  1. siftDown(A, root, end)
  2. while 2 · root + 1 < end
  3. left ← 2 · root + 1
  4. right ← left + 1
  5. largest ← root
  6. if A[left] > A[largest]: largest ← left
  7. if right < end and A[right] > A[largest]: largest ← right
  8. if largest = root: return
  9. swap A[root], A[largest]
  10. root ← largest

La riga evidenziata corrisponde all’operazione descritta nel simulatore. I dettagli di gestione degli indici sono intenzionalmente semplificati.

Studio della complessità

Caso miglioreΘ(n log n)

La fase di estrazione esegue n−1 ripristini del heap, ciascuno fino a log n livelli: Θ(n log n) anche nel caso migliore standard.

Caso medioΘ(n log n)

Build-heap costa Θ(n); le estrazioni dominano con Θ(n log n).

Caso peggioreΘ(n log n)

L’altezza del heap è sempre Θ(log n), quindi il limite peggiore resta Θ(n log n).

Spazio ausiliarioΘ(1)

Gli scambi avvengono nello stesso array e la versione iterativa usa Θ(1) spazio. Gli scambi a lunga distanza distruggono la stabilità.

Proprietà in breve

Non stabile

La stabilità riguarda l’ordine relativo degli elementi con chiave uguale.

In place

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