# Heap / Priority Queue — डेटा स्ट्रक्चर और एल्गोरिदम

Source: https://www.geekswithgeeks.com/hi/dsa/heap

> Array में रखा पूर्ण binary tree जहाँ root हमेशा min (या max) होता है।

## Heap गुण

Min-heap में हर parent ≤ उसके children, तो सबसे छोटा तत्व root पर — peek `O(1)`। Push और pop तत्व को ऊपर/नीचे *bubble* करके गुण बहाल करते हैं `O(log n)` में। Array में: `i` के children `2i+1`, `2i+2`।

## अस्पताल triage

मरीज़ आगमन क्रम में नहीं, गंभीरता से देखे जाते हैं। सबसे ज़रूरी हमेशा अगला, और नया मरीज़ जोड़ने पर सिर्फ़ स्थानीय पुनःक्रम।

## Heap से Top-K

आकार-K min-heap रखें; K सबसे बड़े में सबसे छोटा root पर बैठता है और पहले निकाला जाता है।

```python
import heapq
def k_largest(nums, k):
    h = []
    for n in nums:
        heapq.heappush(h, n)
        if len(h) > k:
            heapq.heappop(h)   # drop the smallest
    return sorted(h, reverse=True)
```

Output:

```
k_largest([3,1,5,12,2,11], 3) -> [12, 11, 5]
```

## कब उपयोग करें

"K सबसे बड़े/छोटे", "stream का median", "K sorted lists merge", Dijkstra, और कोई भी scheduler जिसे हमेशा वर्तमान सर्वश्रेष्ठ वस्तु चाहिए।