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.
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.
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.
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.
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.
Ett bibliotek med IT-intervjufrågor och detaljerade svar — från Junior till Senior.
Donera