En binary heap är ett fullständigt binärt träd lagrat i en array som upprätthåller heap-egenskapen: i en min-heap är varje förälder ≤ sina barn, så minimumet är alltid vid roten. Det gör det till standardimplementeringen av en prioritetskö.
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
| Operation | Tid |
|---|---|
| peek min/max | O(1) |
| push (insert) | O(log n) |
| pop (extract) | O(log n) |
| build heap från n element | O(n) |
En heap ger dig nästa viktigaste element omedelbar utan att hålla allt helt sorterat, vilket är mycket billigare än omsortering.
Det är grunden för prioritetsdrivna algoritmer och ett vanligt intervjuverktyg för "k största/minsta"-frågor.