ہیپ کیا ہے اور یہ ترجیح والی قطار (priority queue) کو کیسے نافذ کرتا ہے؟

Question

IT Interview Practice · Accepted Answer

ایک **binary heap** ایک مکمل binary tree ہے جو ایک array میں محفوظ ہوتا ہے اور **heap property** کو برقرار رکھتا ہے: ایک **min-heap** میں، ہر والد نوڈ اپنے بچوں سے ≤ ہوتا ہے، اس لیے **کم سے کم value ہمیشہ root پر ہوتی ہے**۔ یہ **priority queue** کو نافذ کرنے کا معیار بناتا ہے۔

## Array layout

```text
       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
```

## Operations

```python
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) |

## کب استعمال کریں

- **ترتیب دینا** ترجیح کے لحاظ سے (مثلاً OS task schedulers)۔
- **Dijkstra / Prim** shortest-path اور MST الگورتھم۔
- **Top-K** مسائل اور streaming medians۔
- **Heap sort** (in-place O(n log n))۔

## یہ اہم کیوں ہے

ایک heap آپ کو اگلی سب سے اہم چیز فوری طور پر دیتا ہے بغیر ہر چیز کو مکمل طور پر sorted رکھے، جو دوبارہ sort کرنے سے بہت سستا ہے۔

yह priority-driven الگورتھم کی بنیاد ہے اور "k largest/smallest" سوالات کے لیے انٹرویو میں بار بار استعمال ہوتا ہے۔

Operation	Time
peek min/max	O(1)
push (insert)	O(log n)
pop (extract)	O(log n)
build heap from n items	O(n)

Array layout

Operations

پیچیدگی

کب استعمال کریں

یہ اہم کیوں ہے

متعلقہ سوالات