Home / Blog / Heap Top-K Interview Pattern

Heap Top-K Interview Pattern

Published 2026-09-30 · Luna Interview

Heap top-k interview problems show up as “k largest,” “k most frequent,” “k closest,” or streaming “always return the median/top.” The pattern is less about memorizing heapq API and more about choosing min-heap of size k vs sorting vs Quickselect—and saying why.

The default top-k move

For “k largest in an unsorted array” when k ≪ n:

• Keep a min-heap of size k
• Heap root is the smallest of the current top-k
• For each new value, if it is larger than root, pop and push

Talk track:

“I’ll maintain a min-heap of size k so the root is the threshold for being in the top k. Linear pass, O(n log k).”

For k smallest, symmetric max-heap of size k.

When to pick which tool

Interviewers often accept sort for partial credit; the heap shows you care about log k.

Frequency top-k skeleton

count ← frequency map of values
heap ← empty min-heap of (freq, value) size up to k
for each (value, freq) in count:
  push into heap
  if heap size > k: pop
return heap contents

Narrate why min-heap on frequency: you discard the least frequent when over capacity.

k closest / custom distance

Define the comparison key explicitly:

“Heap entries are (distance, point); I’ll keep a max-heap of size k by distance so I can evict the farthest.”

Language detail: some libraries only give min-heaps—negate distance to simulate max-heap and say so.

First five minutes

1. Restate: k largest vs k frequent vs k closest
2. Confirm ties policy if relevant
3. Choose heap vs sort vs Quickselect with complexity
4. Define comparison key
5. Sketch push/pop invariant (“heap always holds candidates”)

Complexity cheat lines worth saying

• Size-k heap over n items: O(n log k) time, O(k) extra space
• Sort: O(n log n) time, simpler code
• Counting sort style only if value universe is special
• Building a heap of n then popping k: O(n + k log n)—fine, slightly different shape

Pick one and stick to it unless asked to optimize further.

Common bugs

• Using max-heap when you meant min-heap for k largest (keeps the wrong side)
• Off-by-one: heap size k vs k+1 before pop
• Pushing indices without values (or the reverse) and comparing wrong fields
• Forgetting empty input / k == 0 / k >= n (return sorted copy of all)
• Mutating the heap while iterating the same structure carelessly
• In frequency problems, heapifying values instead of frequencies

Streaming and “design” flavors

If the prompt is a class with add and getTopK:

• Store the heap as a field
• On add, apply the same size-k eviction
• Clarify whether getTopK must be sorted each call

For median maintenance, mention two-heap balance briefly; do not implement unless that is the problem.

Freeze recovery

1. Write the invariant: “heap has at most k best so far”
2. On paper, process a 5-element array with k=3
3. Implement push/pop only—no fancy wrappers
4. If language API is fuzzy, say you will use a sorted list of size k as temporary stand-in, then upgrade

Talk track:

“I’m going to get the size-k eviction right on an example, then code it.”

Practice plan

Soft practice note

Top-k is a composure pattern: clear invariant, small API surface, honest complexity. If you want a Chrome side panel to rehearse the min-heap-of-size-k talk track while you practice, Luna Interview supports that calm practice loop. Use it to build fluency—not to skip heap fundamentals or to violate interview rules.

Day-of checklist

• [ ] k largest vs frequent vs closest named
• [ ] Min-heap vs max-heap justified
• [ ] Size capped at k
• [ ] Edge cases k=0 / k≥n
• [ ] Complexity O(n log k) spoken
• [ ] Example dry-run done

Keep the heap tiny and the invariant loud—that is the top-k interview pattern.

Rehearse with an AI interview copilot, then browse commonly reported interview questions.