AlgoScope

K-th Largest / Smallest

Keep a min heap of size k. The root is the k-th largest after scanning everything.

Heap algorithms, algorithm, intermediate
5 replaces the root 1 and sinks. The root is now 2.325root
5 replaces the root 1 and sinks. The root is now 2.325root

K-th Largest: Third largest of nine

Decision, step 5 of 11

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 LargestMin heap of size k.
  • K-th SmallestMax heap of size k.