Heap / Priority Queue

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.

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.