Motivazione

Heap Sort usa un heap binario per trovare ripetutamente l’elemento più grande rimasto in O(log n), ottenendo un ordinamento affidabile in O(n log n).

Perché imparare Heap Sort?

• O(n log n) garantito: a differenza di Quick Sort, non ha un caso peggiore O(n²).
• In-place: ordina all’interno dell’array originale e richiede solo O(1) di memoria aggiuntiva, a differenza di Merge Sort.
• Intuizione sugli heap: rafforza la comprensione di come un heap viene memorizzato in un array e di come l’operazione sift-down lo mantenga valido.

Se hai seguito il corso Heap in questa serie, Heap Sort è quella struttura dati messa al lavoro come algoritmo di ordinamento.