Hur fungerar heap sort?

Question

Accepted Answer

**Heap sort** bygger en **binär heap** från arrayen, extraherar sedan upprepade gånger maximumet för att producera sorterad ordning. Det körs i **O(n log n)** och är **in-place**.

## Idén

En max-heap behåller det största elementet vid roten. Bygg heapen (O(n)), byt sedan roten till slutet, krympa heapen och re-heapifiera (sift down) — n gånger.

## Exempel

```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 genom att sifta ned inom arrayen.

## Komplexitet

- **Tid:** O(n log n) i alla fall. **Utrymme:** O(1) in-place.

## När man ska använda / fallgropar

Använd när du behöver **garanterad O(n log n)** *och* **O(1) extra minne** (merge sort kräver O(n); quicksort riskerar O(n²)). Den är **inte stabil** och har dålig cache-lokalitet, så den är ofta långsammare i praktiken än quicksort. Samma heap driver **prioritetsköer** och att hitta top-k-element.

## Varför det spelar roll

Heap sort är den enda vanliga sortering som är både värsta fall O(n log n) och in-place, vilket gör den värdefull i minnesbegränsade eller garanterade inställningar.

Heap-strukturen är brett användbar — prioritetsköer, Dijkstras algoritm och streaming top-k.

Det cementerar idén att rätt datastruktur gör en algoritm effektiv.