K-th Largest / Smallest
Keep a min heap of size k; the root is the k-th largest after scanning everything.
Decision · step 5 of 11K-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.
What you will see
Values enter a size-k heap; anything smaller than the root bounces off.
Cost
| Best | O(n log k) |
|---|---|
| Average | O(n log k) |
| Worst | O(n log k) |
| Space | O(k) |
How you work with it here
play it through, step one change at a time, scrub to any step, run it on your own input, predict what happens next, try operations in any order.
Screen readers: Nodes announce value, parent and children; each step announces the comparison and whether the value moves up or down.
Reduced motion: Swaps become value crossfades in both the tree and the array view.
Before this
Related
Variants
- K-th Largest Min heap of size k.
- K-th Smallest Max heap of size k.