Mikä on keko ja kuinka se toteuttaa prioriteettijonon?

Question

Accepted Answer

**Binäärikeko** on täydellinen binääripuu, joka on tallennettu taulukkoon ja säilyttää **keon ominaisuuden** (heap property): **minimikekossa** jokainen vanhempi on ≤ sen lapsilleen, joten **minimi on aina juuressa**. Tämä tekee siitä **prioriteettijonon standarditoteutuksen**.

## Taulukon rakenne

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

## Operaatiot

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

## Monimutkaisuus

| Operaatio | Aika |
|---|---|
| piikit pienin/suurin | O(1) |
| push (lisää) | O(log n) |
| pop (poista) | O(log n) |
| rakenna keko n alkiosta | O(n) |

## Milloin käyttää

- **Ajoitus** prioriteetin mukaan (esim. käyttöjärjestelmän tehtävien ajoitus).
- **Dijkstra / Prim** -algoritmit lyhyimmälle polulle ja MST:lle.
- **Top-K** -ongelmat ja virtaviivainen mediaani.
- **Kekonjärjestys** (in-place O(n log n)).

## Miksi se on tärkeää

Keko antaa sinulle seuraavaksi tärkeimmän kohteen välittömästi ilman, että sinun tarvitsee pitää kaikkea täysin järjestettynä, mikä on paljon halvempaa kuin uudelleenjärjestys.

Se on prioriteettiohjattujen algoritmien selkäranka ja usein käytetty haastattelutyökalu "k suurin/pienin" -kysymyksissä.

Operaatio	Aika
piikit pienin/suurin	O(1)
push (lisää)	O(log n)
pop (poista)	O(log n)
rakenna keko n alkiosta	O(n)