ਹੀਪ ਕੀ ਹੈ ਅਤੇ ਇਹ ਪ੍ਰਾਇਓਰਿਟੀ ਕਿਊ ਨੂੰ ਕਿਵੇਂ ਲਾਗੂ ਕਰਦਾ ਹੈ?

Question

Accepted Answer

ਇੱਕ **binary heap** ਇੱਕ ਸੰਪੂਰਨ binary tree ਹੈ ਜੋ ਇੱਕ array ਵਿੱਚ ਸਟੋਰ ਕੀਤਾ ਜਾਂਦਾ ਹੈ ਜੋ **heap property** ਨੂੰ maintain ਕਰਦਾ ਹੈ: ਇੱਕ **min-heap** ਵਿੱਚ، ਹਰ parent ਆਪਣੇ children ਤੋਂ ≤ ਹੁੰਦਾ ਹੈ، ਇਸ ਲਈ **minimum ਹਮੇਸ਼ਾ root ਉੱਤੇ ਹੁੰਦਾ ਹੈ**। ਇਹ ਇਸ ਨੂੰ **priority queue** ਦਾ standard implementation ਬਣਾਉਂਦਾ ਹੈ।

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

## Complexity

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

## When to use

- **Scheduling** by priority (e.g. OS task schedulers)।
- **Dijkstra / Prim** shortest-path ਅਤੇ MST algorithms.
- **Top-K** problems ਅਤੇ streaming medians।
- **Heap sort** (in-place O(n log n))।

## ਇਹ ਕਿਉਂ ਮਹੱਤਵਪੂਰਨ ਹੈ

ਇੱਕ heap ਤੁਹਾਨੂੰ ਸਭ ਕੁਝ ਨੂੰ ਪੂਰੀ ਤਰ੍ਹਾਂ sorted ਰੱਖੇ ਬਿਨਾਂ ਤੁਰੰਤ ਅਗਲੀ-ਸਭ ਤੋਂ ਮਹੱਤਵਪੂਰਨ ਚੀਜ਼ ਦਿੰਦਾ ਹੈ، ਜੋ re-sorting ਨਾਲੋਂ ਬਹੁਤ ਸਸਤਾ ਹੈ।

ਇਹ priority-driven algorithms ਦੀ ਰੀੜ੍ਹ ਦੀ ਹੱਡੀ ਹੈ ਅਤੇ "k largest/smallest" ਸਵਾਲਾਂ ਲਈ ਇੱਕ ਲਗਾਤਾਰ interview ਟੂਲ ਹੈ।

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