Kaj je heap in kako implementira prioritetno vrsto?

Question

IT Interview Practice · Accepted Answer

**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".

Operacija	Čas
peek min/max	O(1)
push (insert)	O(log n)
pop (extract)	O(log n)
build heap iz n elementov	O(n)

Razporeditev matrike

Operacije

Časovna zahtevnost

Kdaj ga uporabljati

Zakaj je pomembno

Povezana vprašanja