Hvordan fungerer heap sort?

Question

Accepted Answer

**Heap sort** bygger en **binary heap** fra arrayen, og trekker deretter gjentatte ganger ut maksimum for å produsere sortert rekkefølge. Det kjører i **O(n log n)** og er **in-place**.

## Ideen

En max-heap holder det største elementet ved roten. Bygg heapen (O(n)), bytt deretter roten til enden, krympe heapen, og re-heapify (sift down) — n ganger.

## 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 gjør det på plass ved å sive ned innenfor arrayen.

## Kompleksitet

- **Tid:** O(n log n) i alle tilfeller. **Plass:** O(1) in-place.

## Når det skal brukes / fallgruver

Bruk når du trenger **garantert O(n log n)** *og* **O(1) ekstra minne** (merge sort trenger O(n); quicksort risikerer O(n²)). Det er **ikke stabilt** og har dårlig cache-lokalitet, så det er ofte tregere i praksis enn quicksort. Den samme heapen driver **priority queues** og å finne de topp-k elementene.

## Hvorfor det er viktig

Heap sort er den eneste vanlige sortering som er både worst-case O(n log n) og in-place, noe som gjør det verdifullt i minnebegrensede eller garanterte innstillinger.

Heap-strukturen under er bredt nyttig — priority queues, Dijkstras algoritme og streaming top-k.

Det befester ideen om at riktig datastruktur gjør en algoritme effektiv.