Heaps, Top-K, And Streaming Selection

What's being tested

Heaps, top-k selection, and streaming aggregation test whether you can avoid full sorting when only a small ranked subset is needed. Interviewers look for correct data-structure choice, precise O(...) complexity, and clean handling of ties, duplicates, and incremental updates.

Patterns & templates

• Top-k frequent elements — count with HashMap, maintain size-k min-heap; O(n log k) time, O(n) space.

• Bucket sort for frequencies — when counts are integers in [1,n], use frequency buckets for O(n) time; watch memory tradeoffs.

• Streaming median — use max-heap for lower half and min-heap for upper half; rebalance so sizes differ by at most one.

• Per-key top-k — map each key to a bounded min-heap, e.g. top three scores per student; O(n log k) with tiny k.

• Meeting rooms — sort intervals by start time, track earliest ending meeting in min-heap; heap size equals rooms needed.

• Tie-breaking discipline — define comparator explicitly: frequency first, then value/order if required; avoid nondeterministic heap output.

• Heap API fluency — know heappush, heappop, heapreplace, and negative-value max-heap simulation in Python.

Common pitfalls

Pitfall: Sorting everything with O(n log n) when a bounded heap gives O(n log k) and is the expected optimization.

Pitfall: Forgetting to rebalance two heaps in streaming median after every insert, causing wrong medians after skewed input.

Pitfall: Returning heap contents directly when the problem requires sorted output; pop or sort the final k elements if order matters.

Practice these

The practice cards below cover the canonical variants — solve all of them and time yourself.