ایک binary heap ایک مکمل binary tree ہے جو ایک array میں محفوظ ہوتا ہے اور heap property کو برقرار رکھتا ہے: ایک min-heap میں، ہر والد نوڈ اپنے بچوں سے ≤ ہوتا ہے، اس لیے کم سے کم value ہمیشہ 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
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 رکھے، جو دوبارہ sort کرنے سے بہت سستا ہے۔
yह priority-driven الگورتھم کی بنیاد ہے اور "k largest/smallest" سوالات کے لیے انٹرویو میں بار بار استعمال ہوتا ہے۔