Come funziona?

Un heap binario risiede in un normale array. Per il nodo all'indice i (con indice base 0), i figli si trovano agli indici 2*i + 1 e 2*i + 2. Questo sistema di indicizzazione è il trucco che permette a un albero di risiedere in un array.

Procedimento passo passo:

1. Costruisci un max-heap: riordina l'array in modo che ogni genitore sia >= dei suoi figli. Il valore più grande finisce all'indice 0.
2. Estrai il massimo: scambia la radice (il valore più grande) con l'ultimo elemento dell'heap, poi riduci l'heap di uno, così il valore più grande rimane parcheggiato alla fine, nella sua posizione definitiva nell'array ordinato.
3. Ripara con sift-down: la nuova radice potrebbe trovarsi nella posizione sbagliata, quindi falla scendere (scambiala con il figlio più grande e ripeti) finché la proprietà dell'heap non viene ripristinata.
4. Ripeti finché l'heap non è vuoto. L'array è ora ordinato in ordine crescente.

Esempio su [4, 10, 3, 5, 1]:

• Costruisci un max-heap: [10, 5, 3, 4, 1].
• Sposta 10 alla fine scambiandolo con la radice e fallo scendere, poi ripeti per 5, 4, 3.
• Risultato: [1, 3, 4, 5, 10].