હીપ શું છે અને તે પ્રાધાન્ય કતાર કેવી રીતે અમલમાં મૂકે છે?

Question

Accepted Answer

A **binary heap** એ એક સંપૂર્ણ દ્વિસંગી વૃક્ષ છે જે એક array માં સંગ્રહિત છે જે **heap property** જાળવી રાખે છે: **min-heap** માં, દરેક માતા-પિતા તેના બાળકો કરતા ≤ છે, તેથી **ન્યુનતમ હંમેશા મૂળમાં છે**. આ **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
```

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

- **શેડ્યુલિંગ** પ્રાધાન્ય દ્વારા (દા.ત. OS કાર્ય સમયપત્રણ).
- **Dijkstra / Prim** સૌથી ટૂંકો પાથ અને MST અલ્ગોરિધમ.
- **Top-K** સમસ્યાઓ અને સ્ટ્રીમિંગ મધ્યમ.
- **Heap sort** (સ્થાને O(n log n)).

## તેમાં મહત્ત્વ કેમ છે

હીપ તમને પરવર્તી-સૌથી-મહત્ત્વપૂર્ણ વસ્તુ તરત જ આપે છે બધું સંપૂર્ણરીતે સૂચિબદ્ધ કર્યા વિના, જે પુનરાવર્તિત કરતા ઘણું સસ્તું છે.

હીપ એ પ્રાધાન્ય-નિર્દેશિત અલ્ગોરિધમ્સનો ધોરણ છે અને "k સૌથી મોટો/સૌથી નાનો" પ્રશ્નો માટે વારંવાર સાક્ષાત્કાર સાધન છે.

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