Heap sort buduje binarny stos z tablicy, a następnie wielokrotnie wyodrębnia maksimum, aby uzyskać posortowaną kolejność. Działa w O(n log n) i jest na miejscu.
Max-stos przechowuje największy element w korzeniu. Zbuduj stos (O(n)), a następnie zamień korzeń na koniec, zmniejsz stos i ponownie uheapify (sift down) — n razy.
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]
Klasyczna implementacja robi to na miejscu, wykonując sift down w obrębie tablicy.
Używaj, gdy potrzebujesz gwarantowanego O(n log n) i O(1) dodatkowej pamięci (merge sort potrzebuje O(n); quicksort ryzykuje O(n²)). Jest niestabilny i ma słabą lokalność pamięci podręcznej, więc w praktyce jest często wolniejszy niż quicksort. Ten sam stos zasilą kolejki priorytetów i wyszukiwanie top-k elementów.
Heap sort jest jedynym powszechnym sortowaniem, które jest zarówno najgorszym przypadkiem O(n log n) jak i na miejscu, co czyni go cennym w ustawieniach ograniczonych pamięcią lub z gwarantowanym ograniczeniem.
Struktura stosu poniżej jest szeroko przydatna — kolejki priorytetów, algorytm Dijkstry i top-k streamingu.
Utrwala ideę, że prawidłowa struktura danych sprawia, że algorytm jest wydajny.