Hoe werkt heap sort?

Question

Accepted Answer

**Heap sort** bouwt een **binary heap** uit de array, haalt vervolgens herhaaldelijk het maximum uit om gesorteerde volgorde te produceren. Het draait in **O(n log n)** en is **in-place**.

## Het idee

Een max-heap houdt het grootste element aan de wortel. Bouw de heap (O(n)), verwissel vervolgens de wortel naar het einde, verklein de heap en herpelletiseer (sift down) — n keer.

## Voorbeeld

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

Een klassieke implementatie doet het in plaats door sift down binnen de array.

## Complexiteit

- **Tijd:** O(n log n) in alle gevallen. **Ruimte:** O(1) in-place.

## Wanneer te gebruiken / valkuilen

Gebruik wanneer u **guaranteed O(n log n)** *en* **O(1) extra geheugen** nodig hebt (merge sort heeft O(n) nodig; quicksort riskeert O(n²)). Het is **niet stabiel** en heeft slechte cache-lokaliteit, dus het is in de praktijk vaak langzamer dan quicksort. Dezelfde heap ondersteunt **priority queues** en het zoeken naar de top-k elementen.

## Waarom het belangrijk is

Heap sort is de enige veelgebruikte sort die zowel worst-case O(n log n) als in-place is, waardoor het waardevol is in geheugen-beperkte of gegarandeerde instellingen.

De heap-structuur eronder is breed nuttig — priority queues, Dijkstra's algoritme en streaming top-k.

Het verankert het idee dat de juiste gegevensstructuur een algoritme efficiënt maakt.