Ein binärer Heap ist ein vollständiger Binärbaum, der in einem Array gespeichert ist und die Heap-Eigenschaft erhält: in einem Min-Heap ist jeder Elternknoten ≤ seinen Kindern, sodass das Minimum immer an der Wurzel liegt. Dies macht ihn zur Standardimplementierung einer Prioritätswarteschlange.
1 index: 0 1 2 3 4
/ \ array: [1, 3, 5, 8, 4]
3 5 parent(i) = (i-1)//2
/ \ left(i) = 2i+1
8 4 right(i) = 2i+2
import heapq
h = []
heapq.heappush(h, 5) # O(log n) — bubble up
heapq.heappush(h, 1)
heapq.heappush(h, 3)
smallest = h[0] # peek min -> O(1)
heapq.heappop(h) # O(log n) — remove root, sift down -> 1
| Vorgang | Zeit |
|---|---|
| Minimum/Maximum auslesen | O(1) |
| Einfügen (push) | O(log n) |
| Entfernen (pop) | O(log n) |
| Heap aus n Elementen erstellen | O(n) |
Ein Heap gibt dir das nächst-wichtigste Element sofort, ohne alles vollständig sortiert zu halten, was viel günstiger ist als Neusorting.
Es ist das Rückgrat prioritätsgesteuerter Algorithmen und ein häufiges Interview-Werkzeug für "k größte/kleinste"-Fragen.