Heap sort vytvoří binární haldu z pole, poté opakovaně extrahuje maximum a vytvoří seřazený porядок. Běží v O(n log n) a je in-place.
Max-halda uchovává největší prvek v kořeni. Vytvořte haldu (O(n)), poté vyměňte kořen na konec, zmenšete haldu a znovu ji uspořádejte (sift down) — n krát.
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]
Klasická implementace to dělá in-place pomocí sift down v rámci pole.
Používejte, když potřebujete zaručené O(n log n) a O(1) extra paměť (merge sort potřebuje O(n); quicksort riskuje O(n²)). Není stabilní a má špatnou lokalitu cache, takže je v praxi často pomalejší než quicksort. Stejná halda pohání prioritní fronty a hledání top-k prvků.
Heap sort je jediný běžný sort, který je v nejhorším případě O(n log n) a in-place, což ho činí cenným v paměťově omezených nebo zaručených nastaveních.
Struktura haldy je výrazně užitečná — prioritní fronty, Dijkstrův algoritmus a streamovací top-k.
Ztělesňuje myšlenku, že správná datová struktura činí algoritmus efektivním.
Knihovna IT otázek k pohovoru s podrobnými odpověďmi — od Junior po Senior.
Přispět