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.
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.
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.
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.
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.
Et bibliotek af IT-interviewspørgsmål med detaljerede svar — fra Junior til Senior.
Donér