Heaps: The Repeated-Best Machine

One rule, cheap maintenance

A heap (also called a priority queue) is a container built for exactly one job: repeatedly handing you the best remaining item. In a min-heap "best" means smallest; in a max-heap it means largest.

Structurally, a heap is a complete binary tree — every level is full except possibly the last, which fills left to right — obeying one rule: every parent beats its children. In a min-heap, "beats" means "is less than or equal to". That is the entire contract. Siblings are not ordered against each other, and the second-smallest item could be either child of the root.

This deliberately weak promise is the point. Because the heap only guarantees "the champion sits at the root," fixing the structure after an insert or removal only requires walking one root-to-leaf path — O(log n) work — instead of re-sorting everything.

The tree lives in an array

Heaps store the tree flat in an array, level by level, with no pointers at all. The index math is the whole trick:

• children of index i live at 2i + 1 and 2i + 2
• the parent of index i lives at (i - 1) // 2 (integer division)

Take the min-heap stored as [2, 5, 3, 9, 6, 8]:

Index 0 (value 2) has children at indices 1 and 2 (values 5 and 3) — both bigger, rule holds. Index 1 (value 5) has children at indices 3 and 4 (values 9 and 6) — rule holds. Index 2 (value 3) has one child at index 5 (value 8) — rule holds. A valid min-heap, and notice it is not sorted: 3 comes after 5 in the array.

Push and pop

Push appends the new value at the end of the array, then bubbles it up: while it is smaller than its parent, swap. Push 1 into the heap above: it lands at index 6 as a child of 3. Since 1 < 3, swap. Since 1 < 2, swap again. Two swaps and 1 is the new root.

Pop removes the root, moves the last leaf into the root slot, then sinks it down: while it is bigger than its smaller child, swap with that child. Pop from [2, 5, 3, 9, 6, 8]: 2 leaves, 8 jumps to the root giving [8, 5, 3, 9, 6]. The smaller child of 8 is 3, so swap: [3, 5, 8, 9, 6]. 8 has no children now, done.

Both operations touch one path from root to leaf, so both are O(log n). Reading the root (peek) is O(1). One more cost worth memorizing: turning an unordered array of n items into a heap all at once (heapify) is O(n) — cheaper than n individual pushes, because most items sit near the bottom and barely move.

The top-k trick

Here is the single most-tested heap idea. To track the k largest values in a big or streaming input, keep a min-heap of size k. That sounds backwards, so walk through why it works.

The heap holds the current elite group of k values. Its root is the smallest member of that group — the weakest VIP, and also, by definition, the k-th largest overall. When a new value arrives:

• if it is less than or equal to the root, it cannot crack the top k. Reject it in O(1).
• if it is greater than the root, the weakest member is out: pop the root, push the newcomer. O(log k).

Worked example with k = 3 over the stream 4, 5, 8, 2, 3, 10:

1. Push 4, 5, 8 to fill the heap. Root = 4, so the 3rd largest so far is 4.
2. 2 arrives. 2 < 4, rejected. Still {4, 5, 8}.
3. 3 arrives. 3 < 4, rejected.
4. 10 arrives. 10 > 4, so pop 4, push 10. Heap is {5, 8, 10}, root = 5. The 3rd largest of everything seen is 5. Correct.

The rule of thumb: k largest needs a MIN-heap of size k; k smallest needs a MAX-heap of size k. You always keep the opposite kind of heap from the extreme you want, because the root must be the eviction gate. Total cost: O(n log k) time and O(k) space — compare a full sort's O(n log n) time and O(n) space.

One language note: Python's heapq only provides a min-heap. To simulate a max-heap, push negated values and negate again when reading.

import heapq

def k_largest(nums, k):
    heap = []
    for x in nums:
        if len(heap) < k:
            heapq.heappush(heap, x)
        elif x > heap[0]:
            # evict the weakest member, admit the newcomer
            heapq.heapreplace(heap, x)
    return heap  # heap[0] is the k-th largest

When to reach for a heap

The recognition signals, straight from how problems are worded:

• "top k" / "k closest" / "k most frequent" / "kth largest" — size-k heap.
• "stream" or "continuously arriving" — you cannot sort what has not arrived yet; heaps absorb arrivals in O(log k).
• "repeatedly take the best remaining" — scheduling and simulation. Task Scheduler repeatedly runs the most frequent remaining task (max-heap of counts). Last Stone Weight repeatedly smashes the two heaviest stones (max-heap).
• multiple sorted sources merged into one order — k-way merge: keep one candidate per source in a min-heap of size k, pop the global smallest, refill from that source. O(N log k) for N total elements.
• "median of a stream" — two heaps balanced against each other; the next lesson's visualization covers it.

Choosing among heap, sort, and quickselect

What a heap is not

A heap is not a search structure — finding an arbitrary value is O(n), because only the root's position is guaranteed. It is not sorted — if you pop everything one by one you get sorted order, but that is just heapsort, O(n log n). And if a problem needs "closest value to x" or range queries, you want a sorted structure or binary search tree, not a heap.