Come funziona l'ordinamento con heap (heap sort)?

Question

Accepted Answer

**Heap sort** costruisce un **binary heap** dall'array, poi estrae ripetutamente il massimo per produrre l'ordine ordinato. Funziona in **O(n log n)** ed è **in-place**.

## L'idea

Un max-heap mantiene l'elemento più grande alla radice. Costruisci l'heap (O(n)), poi scambia la radice alla fine, riduci l'heap, e ri-heapify (sift down) — n volte.

## Esempio

```python
import heapq

def heap_sort(arr):
    heapq.heapify(arr)               # min-heap in O(n)
    return [heapq.heappop(arr)       # pop smallest n times
            for _ in range(len(arr))]

heap_sort([5, 2, 8, 1, 3])           # -> [1, 2, 3, 5, 8]
```

Un'implementazione classica lo fa in place facendo sift down all'interno dell'array.

## Complessità

- **Tempo:** O(n log n) in tutti i casi. **Spazio:** O(1) in-place.

## Quando usarlo / insidie

Usalo quando hai bisogno di **O(n log n) garantito** *e* **O(1) memoria aggiuntiva** (merge sort richiede O(n); quicksort rischia O(n²)). **Non è stabile** e ha scarsa locality della cache, quindi spesso è più lento in pratica di quicksort. Lo stesso heap alimenta **priority queue** e la ricerca dei top-k elementi.

## Perché è importante

Heap sort è l'unico ordinamento comune che è sia worst-case O(n log n) che in-place, rendendolo prezioso in contesti memory-constrained o con vincoli garantiti.

La struttura heap sottostante è ampiamente utile — priority queue, algoritmo di Dijkstra, e streaming top-k.

Conferma l'idea che la giusta struttura dati rende un algoritmo efficiente.