A binary heap ni mti kamili wa binary uliosadikiwa katika safu inayotunza heap property: katika min-heap, kila mzazi ni ≤ watoto wake, kwa hivyo kiwango cha chini kiko saidia kwa mizizi. Hii inafanya kuwa utekelezaji wa kawaida wa safu na kipaumbele.
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
| Operesheni | Wakati |
|---|---|
| peek min/max | O(1) |
| push (insert) | O(log n) |
| pop (extract) | O(log n) |
| kujenga heap kutoka vipengee n | O(n) |
Heap inakupa kitu kinachofuata muhimu zaidi mara moja bila kuweka kila kitu kilichoandaliwa kabisa, ambayo ni rahisi zaidi kuliko kupanga tena.
Ni msingi wa algorithms inayounganishwa na kipaumbele na zana ya mara kwa mara ya mahojiano kwa swali za "k kubwa/ndogo".
Maktaba ya maswali ya mahojiano ya IT yenye majibu ya kina — kutoka Junior hadi Senior.
Changia