K-th Largest / Smallest
Keep a min heap of size k. The root is the k-th largest after scanning everything.
K-th Largest: Third largest of nine
5 is larger than the root 1, so 1 can no longer be in the top 3. 1 leaves, 5 takes the root and sinks to its level. The new root 2 is the 3rd largest so far.
Cost
- Best
- O(n log k)
- Average
- O(n log k)
- Worst
- O(n log k)
- Space
- O(k)
Before this
Variants
- K-th Largest
- K-th Smallest