En binær heap er et fullstendig binært tre lagret i en array som opprettholder heap-egenskapen: i en min-heap er hver forelder ≤ sine barn, så minimumet er alltid ved roten. Dette gjør den til standardimplementasjonen 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
| Operasjon | Tid |
|---|---|
| peek min/max | O(1) |
| push (insert) | O(log n) |
| pop (extract) | O(log n) |
| build heap fra n elementer | O(n) |
En heap gir deg det neste viktigste elementet øyeblikkelig uten å holde alt fullstendig sortert, noe som er mye billigere enn å re-sortere.
Den er ryggraden i prioritetsdrevne algoritmer og et hyppig intervjuverktøy for "k største/minste" spørsmål.
Et bibliotek av IT-intervjuspørsmål med detaljerte svar — fra Junior til Senior.
Doner