Heaps, Streaming Median, and Top-K Selection

What's being tested

These problems test efficient use of heaps/priority queues and streaming order-statistics to maintain small summaries of large inputs (medians, k-th, top-k). Interviewers probe algorithmic reductions (k-way merge, two-heap median), complexity tradeoffs, and robust handling of duplicates and ties.

Patterns & templates

• Two-heap median: keep a max-heap for lower half and min-heap for upper half; rebalance sizes to differ ≤1; O(log n) per insert.

• Min-heap size-k for top-k: push items, pop when size > k; overall O(n log k) time, O(k) space.

• Max-heap via inversion: if only min-heap available (e.g., heapq), insert negated keys to simulate a max-heap.

• K-way merge for k smallest pairs: push initial pairs (i,0), pop smallest, then push (i,j+1); avoid duplicate exploration with indices.

• Frequency + heap for top-k words: count with hashmap, then maintain min-heap of (freq, word) with tie-break deterministic ordering, O(n + m log k).

• Lazy deletions for streams: mark removed elements in a hashmap and lazily pop stale heap entries to handle deletions efficiently.

Common pitfalls

Pitfall: Forgetting to rebalance the two heaps correctly — median becomes incorrect by one position after several inserts.

Pitfall: Using full sort instead of size-k heap when k << n, causing unnecessary O(n log n) work.

Pitfall: Not encoding tie-breakers in heap keys (e.g., (freq, word)), producing non-deterministic or wrong ordering.

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