एक binary heap एक सम्पूर्ण binary tree हो जो array मा भण्डारण गरिन्छ र heap property को रक्षा गर्छ: एक min-heap मा, हरेक parent यसको सन्तान भन्दा ≤ हुन्छ, त्यसैले न्यूनतम सधैं root मा हुन्छ। यो 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
विस्तृत उत्तरसहित IT अन्तर्वार्ता प्रश्नहरूको पुस्तकालय — जुनियरदेखि सिनियरसम्म।
दान गर्नुहोस्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) |
एक heap ले तपाईलाई अगलो-सबैभन्दा-महत्त्वपूर्ण वस्तु तुरन्त दिन्छ बिना सबै कुरा पूर्णरूपमा sorted राख्नुपर्ने, जो re-sorting भन्दा धेरै सस्तो छ।
यो priority-driven algorithms को रीढ हो र "k largest/smallest" प्रश्नहरूको लागि बारम्बार interview tool हो।