Binary Heaps & Top-K

Why Pointerless Complete Trees Win in Practice

A Priority Queue is an abstract contract (“insert items with priorities; always hand me the highest-priority item next”). A Binary Heap is the concrete data structure behind Python’s heapq, C++’s std::priority_queue, and Dijkstra’s frontier.

Instead of allocating Node(val, left, right) objects scattered across memory, a binary heap packs a complete binary tree (filled top-to-bottom, left-to-right with zero gaps) into a single contiguous array heap[0 .. n-1]. For any 0-based index i:

• Parent index: (i - 1) // 2 (for i > 0)
• Left child index: 2 * i + 1
• Right child index: 2 * i + 2

And for a Min-Heap, every node obeys a single local invariant:

heap[parent] <= heap[child]

Notice what the heap refuses to sort: left and right cousins do not care who is smaller! By maintaining just enough order to guarantee heap[0] is the global minimum, push and pop only touch one root-to-leaf path of height ⌊log₂ n⌋.

Sift-Up (heappush) and Sift-Down (heappop)

1. heappush(x) — O(log n): Append x at the end of the array (heap[n]) to preserve the complete-tree shape, then sift up (swap with parent while x < heap[parent]).
2. heappop() — O(log n): Save the minimum heap[0], move the last leaf heap.pop() into heap[0], and sift down (swap with the smaller of its two children until <= both children).
3. heapify(arr) — O(n): Starting from the last non-leaf (n // 2) - 1 down to 0, sift each subtree down. Because 50% of nodes sit at height 0 (leaves) and 25% sit at height 1, the geometric work sums to O(n)!

The Streaming Top-K Pattern (O(n log k) Time, O(k) RAM)

Suppose you scan 50 million log files to find the 3 largest (k = 3). Sorting costs O(n log n) time and O(n) memory; building a max-heap of all n files still stores 50,000,000 entries.

Instead, keep a Min-Heap of size k:

• heap[0] is always the smallest member currently inside the Top-k club (the gatekeeper).
• Any incoming file with size <= heap[0] cannot beat even the weakest finalist — ignore it in O(1)!
• Any incoming file with size > heap[0] evicts the gatekeeper and sifts into place via heapreplace in O(log k).

from heapq import heappush, heapreplace


def largest_files(files, k: int = 3) -> list[tuple[int, str]]:
    """Return up to k records, largest first, in O(n log k) time and O(k) space."""
    if k < 0:
        raise ValueError("k must be nonnegative")
    if k == 0:
        return []

    heap: list[tuple[int, str]] = []
    for size, name in files:
        entry = (size, name)
        if len(heap) < k:
            heappush(heap, entry)
        elif size > heap[0][0]:
            # Atomically pops heap[0] and pushes entry in one sift-down pass!
            heapreplace(heap, entry)

    return sorted(heap, reverse=True)

Two Essential Python heapq Idioms for Interviews

• Max-Heap in Python: heapq only implements a min-heap. For numeric priorities, negate the key on push and pop (heappush(h, -val) and -heappop(h)).
• Safe Tuple Tie-Breaking: When pushing (priority, item) where item isn’t comparable (like a custom graph node or ListNode), insert a monotonic counter (priority, tie_id, item) so Python never attempts item1 < item2 when two priorities tie.