Heaps, Priority Queues, and Top-K Selection

What's being tested

Top-K selection with heaps, priority queues, and ordered traversal: count or generate candidates, define an exact comparator, then return only the best k. Interviewers probe whether you can avoid full sorting when unnecessary, handle tie-breaking correctly, and adapt the same pattern to streams, coordinates, prefix search, and sorted-array pair generation.

Patterns & templates

• Frequency map + heap — count with HashMap, maintain size-k min-heap; O(n log k) time, O(m + k) space.

• Comparator discipline — encode primary and secondary keys explicitly, e.g. frequency desc, word lex asc, distance asc; test ties before coding.

• Top-K from stream — update counts incrementally, use lazy heap entries or balanced tree; avoid assuming heap entries auto-update after count changes.

• K smallest pairs — push (i,0) for each first-array index, pop smallest sum, then push (i,j+1); O(k log min(k,n)).

• Distance ranking — compare squared distance x*x + y*y to avoid sqrt; watch integer overflow in Java/C++.

• Autocomplete topK — combine Trie prefix lookup with per-node cached top candidates or DFS + heap; cache improves query time but complicates updates.

• Bottom-K variant — invert comparator or use max-heap of size k; don’t rewrite the whole solution when only ordering changes.

Common pitfalls

Pitfall: Sorting all candidates with O(n log n) when k is small; say why O(n log k) is better.

Pitfall: Implementing an inconsistent comparator, especially for equal frequencies or equal distances, causing nondeterministic output.

Pitfall: Forgetting streaming updates invalidate old heap entries; use lazy deletion by checking current count on pop.

Practice these

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