Top K And Heaps

What's being tested

These problems test top-k selection: choosing a bounded set of best candidates without fully sorting all input. You must recognize when to use a size-k heap, BST traversal, quickselect, or a heap-backed streaming design, then explain correctness, tie-breaking, and complexity.

Patterns & templates

• Size-k min-heap for k-th largest or top-k values: push each item, pop when size exceeds k; O(n log k) time and O(k) space.

• Size-k max-heap for k smallest or closest candidates; define the root as the worst retained item so replacement is constant-time.

• For k closest BST values, use inorder traversal’s sorted order with two pointers, predecessor/successor stacks, or a bounded heap; handle duplicates and target ties explicitly.

• Quickselect finds the k-th order statistic in average O(n) time and O(1) auxiliary space, but worst-case O(n²) requires randomized pivots or median-of-medians.

• For sorted output, separate selection from presentation: extract heap contents and sort them, adding O(k log k) after O(n log k) selection.

• State edge conditions before coding: k <= 0, k > n, empty input, duplicate values, non-integer targets, and whether “closest” means absolute distance.

• For k-pair generation, seed a min-heap with one candidate per row and advance the smallest pair’s row pointer; avoid inserting duplicate states.

Common pitfalls

Pitfall: Sorting everything for a top-k request works but misses the intended O(n log k) solution and wastes memory when k << n.

Pitfall: Using the wrong heap polarity or comparing only values can discard the better candidate when distances tie; encode the full ordering key.

Pitfall: Claiming quickselect is always linear; distinguish average-case O(n) from worst-case O(n²) and explain when deterministic behavior matters.

Practice these

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