Cum funcționează heap sort?

Question

Accepted Answer

**Heap sort** construiește un **heap binar** din matrice, apoi extrage în mod repetat maximul pentru a produce ordine sortată. Funcționează în **O(n log n)** și este **in-place**.

## Ideea

Un max-heap ține cel mai mare element la rădăcină. Construiți heap-ul (O(n)), apoi schimbați rădăcina cu sfârșitul, micșorați heap-ul și re-heapify (sift down) — de n ori.

## Exemplu

```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]
```

O implementare clasică o face pe loc prin sift down în matrice.

## Complexitate

- **Timp:** O(n log n) în toate cazurile. **Spațiu:** O(1) in-place.

## Când să utilizați / capcane

Folosiți când aveți nevoie de **O(n log n) garantat** *și* **O(1) memorie suplimentară** (merge sort necesită O(n); quicksort riscă O(n²)). Este **instabil** și are localitate cache slabă, deci este adesea mai lent în practică decât quicksort. Același heap alimentează **cozile de prioritate** și găsirea elementelor top-k.

## De ce este important

Heap sort este singura sortare comună care este atât caz cel mai rău O(n log n) cât și in-place, ceea ce o face valoroasă în setări cu memorie limitată sau cu limită garantată.

Structura de heap de dedesubt este larg utilă — cozile de prioritate, algoritmul lui Dijkstra și top-k streaming.

Cimentează ideea că structura de date corectă face un algoritm eficient.