# Heap / Priority Queue — Data Structures & Algorithms

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

> A complete binary tree kept in an array where the root is always min (or max).

## The heap property

In a min-heap every parent ≤ its children, so the smallest element is at the root — peek is `O(1)`. Push and pop restore the property by *bubbling* an element up or down in `O(log n)`. Stored in an array: children of `i` are `2i+1`, `2i+2`.

## Hospital triage

Patients aren't seen in arrival order but by severity. The most urgent is always next, and adding a new patient just re-sorts locally.

## Top-K with a heap

Keep a size-K min-heap; the smallest of the K largest sits at the root and gets evicted first.

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

## When to reach for it

"K largest/smallest", "median of a stream", "merge K sorted lists", Dijkstra, and any scheduler that always needs the current best item.