En binær heap er et komplet binært træ gemt i et array, som opretholder heap-egenskaben (heap property): i en min-heap er hver forælder ≤ sine børn, så minimumet er altid ved roden. Dette gør den til standardimplementeringen af 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
| Operationen | Tid |
|---|---|
| se minimum/maksimum | O(1) |
| push (indsæt) | O(log n) |
| pop (fjern) | O(log n) |
| byg heap ud fra n elementer | O(n) |
En heap giver dig det næstmest vigtige element øjeblikkeligt uden at holde alt fuldt sorteret, hvilket er meget billigere end at sortere igen.
Det er ryggraden i prioritetsdrevne algoritmer og et hyppigt interviewspørgsmål for "k største/mindste"-problemer.
Et bibliotek af IT-interviewspørgsmål med detaljerede svar — fra Junior til Senior.
Donér