Co je halda a jak implementuje frontu s prioritou?

Question

Accepted Answer

**Binární halda** je úplný binární strom uložený v poli, který si udržuje **vlastnost haldy** (heap property): v **min-haldě** je každý rodič ≤ než jeho děti, takže **minimum je vždy v kořeni**. Díky tomu je to **standardní implementace fronty s prioritou**.

## Rozložení v poli

```text
       1               index: 0  1  2  3  4
      / \              array: [1, 3, 5, 8, 4]
     3   5             parent(i) = (i-1)//2
    / \                left(i)   = 2i+1
   8   4               right(i)  = 2i+2
```

## Operace

```python
import heapq
h = []
heapq.heappush(h, 5)   # O(log n) — bubble up
heapq.heappush(h, 1)
heapq.heappush(h, 3)
smallest = h[0]        # peek min -> O(1)
heapq.heappop(h)       # O(log n) — remove root, sift down -> 1
```

## Složitost

| Operace | Čas |
|---|---|
| prohlédnutí minima/maxima | O(1) |
| vložení (push) | O(log n) |
| odebrání (pop) | O(log n) |
| vytvoření haldy z n prvků | O(n) |

## Kdy použít

- **Plánování** podle priority (např. plánovače úloh OS).
- **Algoritmy Dijkstra / Prim** pro nejkratší cestu a minimální kostru.
- **Problémy Top-K** a medián ve streamujících datech.
- **Řazení haldou** (in-place O(n log n)).

## Proč je důležité

Halda vám dá nejdůležitější položku okamžitě bez nutnosti mít vše plně seřazené, což je daleko levnější než opakované třídění.

Je to páteř algoritmů řízených prioritami a často se objevuje v rozhovorech na témata "k největších/nejmenších" prvků.

Operace	Čas
prohlédnutí minima/maxima	O(1)
vložení (push)	O(log n)
odebrání (pop)	O(log n)
vytvoření haldy z n prvků	O(n)