Jak funguje heap sort?

Question

Accepted Answer

**Heap sort** vytvoří **binární haldu** z pole, poté opakovaně extrahuje maximum a vytvoří seřazený porядок. Běží v **O(n log n)** a je **in-place**.

## Myšlenka

Max-halda uchovává největší prvek v kořeni. Vytvořte haldu (O(n)), poté vyměňte kořen na konec, zmenšete haldu a znovu ji uspořádejte (sift down) — n krát.

## Příklad

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

Klasická implementace to dělá in-place pomocí sift down v rámci pole.

## Složitost

- **Čas:** O(n log n) ve všech případech. **Prostor:** O(1) in-place.

## Kdy použít / úskalí

Používejte, když potřebujete **zaručené O(n log n)** *a* **O(1) extra paměť** (merge sort potřebuje O(n); quicksort riskuje O(n²)). Není **stabilní** a má špatnou lokalitu cache, takže je v praxi často pomalejší než quicksort. Stejná halda pohání **prioritní fronty** a hledání top-k prvků.

## Složitost

- **Čas:** O(n log n) ve všech případech. **Prostor:** O(1) in-place.

## Proč na tom záleží

Heap sort je jediný běžný sort, který je v nejhorším případě O(n log n) a in-place, což ho činí cenným v paměťově omezených nebo zaručených nastaveních.

Struktura haldy je výrazně užitečná — prioritní fronty, Dijkstrův algoritmus a streamovací top-k.

Ztělesňuje myšlenku, že správná datová struktura činí algoritmus efektivním.