A binary heap shine cikakken bishiyar zwarinwar gida wajen ajiye shi a cikin array wanda ke kiyaye heap property: a cikin min-heap, kowane iyaye ≤ yaye, saboda haka mafi ƙarami koyaushe akwai asusun. Wannan shine aiwatar da priority queue.
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 | Time |
|---|---|
| peek min/max | O(1) |
| push (insert) | O(log n) |
| pop (extract) | O(log n) |
| build heap from n items | O(n) |
A heap yana ba ku kayan gida mafi mahimmanci na jiya nan ba tare da kiyaye komai da banza tsarawa, wanda shine nisa sannu nesa fiye da sake tsarawa.
Gari shine tushe na algorithms da suka bugi mahimmanci da kayan aiki na interview sau da sau don catalan "k mafi girma/mafi ƙarami".