Heap / Top-K

What the heap / top-K pattern is

A heap gives O(log n) insert and O(log n) extract of the minimum (or maximum), with the extreme readable in O(1). That makes it the tool whenever you repeatedly need 'the best remaining thing': the k largest elements, the next smallest among several streams, the most frequent items.

The counterintuitive core: to track the k LARGEST elements, use a MIN-heap of size k. Its root is the weakest of your current champions - the gatekeeper. Each new element fights the gatekeeper: bigger means swap in (pop, push), otherwise discard. After one pass the heap holds exactly the top k, in O(n log k) instead of O(n log n) for full sorting.

How to recognize it

Signals: 'k largest / smallest / closest / most frequent', 'merge k sorted lists/streams', 'schedule the next available', or streaming data where a full sort is impossible because elements keep arriving. If k is small relative to n, the heap's O(n log k) is the point; if k ~ n, just sort.

Know the alternatives to name: quickselect finds the k-th element in average O(n) when a one-shot answer suffices (no streaming), and bucket sort by count solves top-k-frequent in O(n) when frequencies are bounded by n. Offering the trade-off is worth as much as the heap code.

The size-k gatekeeper template

Build nothing up front: push elements until size k, then for each remaining element compare against the root. The heap never exceeds k entries, so memory is O(k) - which is why this works on streams that never end.

# k largest elements of a stream
heap = min-heap
for x in stream:
    if len(heap) < k:
        heap.push(x)
    elif x > heap.peek():     # beats the weakest champion
        heap.pop()
        heap.push(x)
# heap now holds the k largest; root is the k-th largest

K-way merging

To merge k sorted lists, the only candidates for 'next smallest overall' are the k current heads. Keep them in a min-heap: pop the smallest, append it to the output, push its successor from the same list. Every element passes through the heap once: O(N log k) for N total elements - the heap's size is k, not N.

Common pitfalls

Flipping the heap direction: k largest needs a min-heap (evict the weakest), k smallest needs a max-heap. Getting this backwards inverts the answer.

Heapifying all n elements (O(n) memory, O(n log n) drain) when the size-k gatekeeper does it in O(k) memory - the difference is the entire pattern.

Languages with only min-heaps (Python): negate values or use tuple keys for max-heap behavior, and say you are doing it.

Pushing non-comparable tuples: when priorities tie, the heap compares the next tuple field - include an index tiebreaker before any non-comparable payload (classic merge-k-lists crash).

Ignoring quickselect when the interviewer asks for 'better than O(n log k)' on a static array - average O(n) is the expected answer.

Worked examples

heap = min-heap
for x in nums:
    heap.push(x)
    if len(heap) > k:
        heap.pop()          # evict the weakest
return heap.peek()

counts = hash map of value -> frequency
heap = min-heap ordered by count
for (value, count) in counts:
    heap.push((count, value))
    if len(heap) > k: heap.pop()
return values remaining in heap

heap = min-heap of (node.val, i, node) for each list head
dummy = Node(); tail = dummy
while heap not empty:
    (val, i, node) = heap.pop()
    tail.next = node; tail = node
    if node.next: heap.push((node.next.val, i, node.next))
return dummy.next

Check yourself

Try to answer before revealing - retrieving from memory is what makes it stick.

Frequently asked questions