The kth largest, without sorting everything

Given a list of numbers and a value k, report the kth largest number. The kth largest counts duplicates, so in [3, 2, 3, 1] the 2nd largest is 3.

Worked example#

For [3, 2, 1, 5, 6, 4] with k = 2:

Sorted downwards the values are 6 5 4 3 2 1, so the 2nd largest is 5.

The idea#

Sorting the whole list works and costs n log n. It also computes far more than the question asked: you wanted one number and produced a total ordering.

Keep a min-heap of size k instead. Walk the numbers once. Push each one. If the heap now holds more than k, pop the smallest.

At every moment the heap holds the k largest numbers seen so far, and the smallest of those is sitting at the top. So when the walk ends, the top is the answer.

for each value:
    push it
    if the heap is bigger than k: pop the smallest
return the top

Why a min-heap for a largest-k question#

This inversion catches people out, and it is worth pinning down.

You are keeping the k largest. The one you want to throw away when a better candidate arrives is the smallest of the ones you kept. A min-heap puts exactly that at the top, in constant time.

A max-heap would put the biggest at the top, which you never need to remove. So:

• k largest means a min-heap of size k.
• k smallest means a max-heap of size k.

Say it backwards once and it sticks.

What it costs#

Each number is pushed and maybe popped, and heap operations on a heap of size k cost log k. So n log k rather than n log n.

With a million numbers and k = 10, that is the difference between sorting a million things and doing a million operations on a heap of ten. And the memory is k, not n, which is why this works on a stream that never ends and could not be sorted at all.

Constraints#

• 1 <= k <= n <= 100000
• -1000000000 <= nums[i] <= 1000000000