Binarni heap je popolno binarno drevo shranjeno v matriki, ki vzdržuje heap lastnost: v min-heap je vsak starš ≤ svojim otrokom, zato je minimum vedno v korenu. To ga naredi za standardno implementacijo prioritetne vrste.
Razporeditev matrike
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
Operacije
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
Časovna zahtevnost
| Operacija | Čas |
|---|---|
| peek min/max | O(1) |
| push (insert) | O(log n) |
| pop (extract) | O(log n) |
| build heap iz n elementov | O(n) |
Kdaj ga uporabljati
- Razporejanje po prioriteti (npr. OS task schedulers).
- Dijkstra / Prim algoritmi za najkrajšo pot in MST.
- Top-K problemi in streaming mediani.
- Heap sort (in-place O(n log n)).
Zakaj je pomembno
Heap ti da naslednji najpomembnejši element takoj brez, da bi hranil vse popolnoma sortirano, kar je veliko ceneje kot ponovno sortiranje.
Je osnova prioritetnih algoritmov in pogost interview orodje za vprašanja "k največjih/najmanjših".