एक binary heap एक पूर्ण बाइनरी ट्री है जो एक array में संग्रहीत है जो heap property को बनाए रखता है: min-heap में, प्रत्येक माता-पिता अपने बच्चों से ≤ होता है, इसलिए न्यूनतम हमेशा रूट पर होता है। यह 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) |
एक हीप आपको अगली सबसे महत्वपूर्ण चीज़ तुरंत देता है बिना सब कुछ पूरी तरह सॉर्ट किए, जो पुनः सॉर्ट करने से बहुत सस्ता है।
यह प्राथमिकता-संचालित एल्गोरिदम की रीढ़ है और "k सबसे बड़ा/सबसे छोटा" प्रश्नों के लिए एक बार-बार साक्षात्कार उपकरण है।