Kuinka keko-lajittelu toimii?

Question

Accepted Answer

**Keko-lajittelu** rakentaa **binäärisen keon** taulukosta ja poimii sitten toistuvasti maksimin tuottaakseen lajitellun järjestyksen. Se toimii **O(n log n)** ja on **paikalla**.

## Idea

Max-keko säilyttää suurimman elementin juuressa. Rakenna keko (O(n)), vaihda sitten juuri loppuun, kutista keota ja uudelleenkeon (sift down) — n kertaa.

## Esimerkki

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

Klassinen toteutus tekee sen paikalla käyttämällä sift down -tekniikkaa taulukon sisällä.

## Monimutkaisuus

- **Aika:** O(n log n) kaikissa tapauksissa. **Tila:** O(1) paikalla.

## Milloin käyttää / Sudenkuopat

Käytä kun tarvitset **taatun O(n log n)** *ja* **O(1) lisämuistia** (merge sort vaatii O(n); quicksort riskii O(n²)). Se **ei ole stabiili** ja sillä on huono välimuistin paikalllisuus, joten se on usein hitaampi käytännössä kuin quicksort. Sama keko tehostaa **prioriteettijonoja** ja top-k elementtien etsintää.

## Miksi se on tärkeää

Keko-lajittelu on ainoa yleinen lajittelu, joka on sekä worst-case O(n log n) että paikalla, mikä tekee siitä arvokasta muistirajappeissa tai taattujen rajojen asetuksissa.

Alainen keko-rakenne on laajasti hyödyllinen — prioriteettijonot, Dijkstran algoritmi ja streaming top-k.

Se vahvistaa ajatusta, että oikea tietorakenne tekee algoritmista tehokkaan.