Interview Pattern Catalog

August 2026 · 18 min read

Almost every heap problem you will be asked is one of seven patterns. This post names them, gives the recognition signal for each, and provides the skeleton. The goal is that reading a problem statement should trigger a pattern within about thirty seconds.

Recognising a Heap Problem

Three signals, any of which should make you consider a heap:

1. “k-th” or “top k” or “k closest” — and k is much smaller than n.
2. Repeated extraction of an extreme from a set that changes — “repeatedly take the smallest…”.
3. A stream, or data too large to sort, where you need an aggregate over what has been seen.

And one strong counter-signal: if the candidate set is fixed, sorting is simpler and usually faster. The heap earns its place only when the set is alive.

Pattern 1: Bounded Top-K

Signal: “find the k largest / smallest / most frequent / closest.”

Key move: a heap of size k ordered opposite to what you want, so the root is the eviction candidate.

std::priority_queue<T, std::vector<T>, std::greater<T>> heap;   // min-heap for k LARGEST
for (const T& x : items) {
    heap.push(x);
    if (heap.size() > k) heap.pop();
}

O(n log k) time, O(k) space. Full treatment in Part 7.

Pattern 2: K-Way Merge

Signal: several sorted sequences, matrices with sorted rows, or “the k-th smallest pair sum.”

Key move: the heap holds one front per sequence; popping one pushes its successor.

for (each sequence s) if (!s.empty()) heap.push({s.front(), s.id, 0});
while (!heap.empty()) {
    auto [val, id, pos] = heap.top(); heap.pop();
    emit(val);
    if (pos + 1 < len(id)) heap.push({seq[id][pos+1], id, pos + 1});
}

O(N log k). See Part 8.

Pattern 3: Two Heaps

Signal: median, percentile, or any balanced split of a growing multiset.

Key move: a max-heap of the lower half and a min-heap of the upper, kept within one element of each other in size.

lo.push(x);                                  // max-heap
hi.push(lo.top()); lo.pop();                 // shuttle to enforce ordering
if (hi.size() > lo.size()) { lo.push(hi.top()); hi.pop(); }

See Part 9.

Pattern 4: Scheduling with a Clock

Signal: intervals, meetings, servers, CPU tasks, anything where resources are occupied then released.

Key move: sort by availability time, keep a heap keyed by the selection rule, and jump the clock rather than ticking it.

sort(items by start / arrival);
while (work remains) {
    admit everything with arrival <= now into the heap;
    if (heap empty) { now = next arrival; continue; }      // jump, never tick
    take heap.top(); advance now;
}

See Part 10.

Pattern 5: Greedy Extraction

Signal: “repeatedly combine / remove the two smallest”, minimum cost to connect, Huffman-shaped problems.

Key move: pop one or two, compute, push the result back.

while (heap.size() > 1) {
    auto a = heap.top(); heap.pop();
    auto b = heap.top(); heap.pop();
    heap.push(combine(a, b));
}

See Part 11.

Pattern 6: Regret / Revocable Greedy

Signal: “maximise the count subject to a constraint”, where an earlier choice may be swapped out later.

Key move: the heap holds your commitments, ordered so the root is the one you would most like to revoke.

for (item in sorted order) {
    if (item fits) { take(item); heap.push(item.cost); }
    else if (!heap.empty() && heap.top() > item.cost) {   // swap improves the state
        undo(heap.top()); heap.pop();
        take(item); heap.push(item.cost);
    }
}

The count never falls and the resource usage strictly drops. See Part 11.

Pattern 7: Lazy Deletion

Signal: a sliding window, or any setting where queued entries become obsolete.

Key move: never erase; verify at the root against an authoritative record and discard stale entries.

while (!heap.empty() && is_stale(heap.top())) heap.pop();
auto best = heap.top();

See Part 12.

Decision Table

Under Interview Conditions

A sequence that reliably works:

1. State the brute force and its cost first. “Sorting gives O(n log n); I think we can do O(n log k).” This shows you know why the heap is an improvement rather than a reflex.
2. Say the direction out loud and justify it. “k largest, so a min-heap of size k — the root is the weakest candidate I'm keeping, which is the one I want to evict.” This is the step interviewers listen for.
3. Handle the empty and k > n cases before coding the main loop.
4. State the complexity in both time and space, and mention the streaming property if it applies — it is often the real reason the heap is right.
5. Mention the alternative. “If everything is in memory and I only need the set unordered, nth_element is O(n) and would beat this.” Knowing when your answer is second-best is a strong signal.