Heap Sort erstellt einen binären Heap aus dem Array und extrahiert dann wiederholt das Maximum, um sortierte Reihenfolge zu erzeugen. Es läuft in O(n log n) und ist in-place.
Ein Max-Heap behält das größte Element an der Wurzel. Erstellen Sie den Heap (O(n)), tauschen Sie dann die Wurzel ans Ende, verkleinern Sie den Heap und führen Sie ein erneutes Heapify (sift down) durch — n-mal.
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]
Eine klassische Implementierung führt dies in-place durch sift down innerhalb des Arrays durch.
Verwenden Sie dies, wenn Sie garantiertes O(n log n) und O(1) zusätzlichen Speicher benötigen (Merge Sort benötigt O(n); Quicksort riskiert O(n²)). Es ist nicht stabil und hat schlechte Cache-Lokalität, sodass es in der Praxis oft langsamer als Quicksort ist. Der gleiche Heap treibt Priority Queues und das Auffinden der Top-k-Elemente an.
Heap Sort ist die einzige gängige Sortierung, die sowohl worst-case O(n log n) als auch in-place ist, was sie in speichergerangten oder garantierten Grenzsituationen wertvoll macht.
Die Heap-Struktur darunter ist breit nützlich — Priority Queues, Dijkstras Algorithmus und Streaming Top-k.
Sie zementiert die Idee, dass die richtige Datenstruktur einen Algorithmus effizient macht.