Hvordan virker heap sort?

Question

Accepted Answer

**Heap sort** bygger en **binær heap** fra arrayet, og henter derefter gentagne gange det maksimale element for at producere sorteret rækkefølge. Det kører i **O(n log n)** og er **in-place**.

## Ideen

En max-heap holder det største element i roden. Byg heapen (O(n)), byt derefter roden til slutningen, formindsk heapen, og re-heapify (sift down) — n gange.

## Eksempel

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

En klassisk implementering gør det in-place ved at sift down inden for arrayet.

## Kompleksitet

- **Tid:** O(n log n) i alle tilfælde. **Plads:** O(1) in-place.

## Hvornår man skal bruge det / faldgruber

Brug det, når du har brug for **garanteret O(n log n)** *og* **O(1) ekstra hukommelse** (merge sort kræver O(n); quicksort risikerer O(n²)). Det er **ikke stabilt** og har dårlig cache-lokalitet, så det er ofte langsommere i praksis end quicksort. Den samme heap driver **prioritetskøer** og finding top-k elementer.

## Hvorfor det betyder noget

Heap sort er den eneste almindelige sortering, der både er worst-case O(n log n) og in-place, hvilket gør det værdifuldt i hukommelseskonstrinerede eller garanterede grænseindstillinger.

Heap-strukturen under huden er bredt nyttig — prioritetskøer, Dijkstras algoritme og streaming top-k.

Det cementerer ideen om, at den rigtige datastruktur gør en algoritme effektiv.