Data Structures & Algorithms
Top K Selection
Bounded-size heap + linear scan. Opposite-polarity rule: min-heap for K-largest, max-heap for K-smallest.
- Problem 01 Kth Largest Element Min-heap of size K; the root is the K-th largest.
- Problem 02 Kth Smallest Element Max-heap of size K; the root is the K-th smallest.
- Problem 03 Sort a Nearly Sorted Array Min-heap of size k+1 slides the window; the root is always the next smallest.
- Problem 04 K Closest Elements to X Max-heap of size K on |value − x|; evict the farthest.
- Problem 05 K Closest Points to Origin Max-heap of size K on x² + y²; evict the farthest.