880. The k Largest Values
Given n values and a number k, print the k largest of them in
DECREASING order. Duplicates count separately, so 7 7 7 with k = 2 prints
7 7.
n = 6, k = 3, values 4 9 1 7 7 2 -> 9 7 7
n = 5, k = 5, values 3 1 4 1 5 -> 5 4 3 1 1
n = 4, k = 2, values -8 -3 -9 -1 -> -1 -3
## What most people try first
Sorting everything and taking the front k. That is correct, costs
O(n log n), and produces n ordered values when only k were wanted. At
n = 200000 and k = 10 it does about 3.5 * 10^6 comparisons to answer a
question that needs far fewer.
The other common attempt is k passes, each finding and removing the current
maximum. That is O(nk), which is 2 * 10^9 when k is large.
## A min-heap of size k, and why the direction feels backwards
Hold the k best values seen so far. When a new value arrives, it should
replace the WORST of the survivors if it beats it. So the heap's job is to
report the worst survivor cheaply, and the worst of the k LARGEST values is
the SMALLEST of them.
That is the whole reason the heap is a MIN-heap even though the question asks for the largest. Getting it the other way round gives a max-heap whose top is the answer itself, which is exactly the value you never want to throw away.
h = empty min-heap
for each value v:
if size(h) < k: push v
else if v > top(h):
pop, then push v
sort what is left, decreasing, and print
## Why it is correct
Claim: after processing any prefix, the heap holds exactly the k largest
values of that prefix (or all of them, if fewer than k have been seen).
It is true after the first k values, trivially. Suppose it holds after some
prefix and a value v arrives. If v is at most the smallest survivor, then
at least k already-seen values are at least v, so v is not in the new
top k and discarding it is right. If v is greater than the smallest
survivor, then the new top k is the old one with that smallest survivor
replaced by v, which is what the code does. The claim carries to the end.
## The cost, and when this actually wins
Each of n values does at most one push and one pop into a heap of size
k, so the total is O(n log k). Against sorting's O(n log n), the win
is real when k is far smaller than n: at n = 200000 and k = 10,
log2 k is about 3 and log2 n is about 18, a factor of six. When k
equals n the two are the same and sorting is simpler. Knowing which regime
you are in is the actual skill.
## The boundary that breaks a careless implementation
The comparison for eviction must be STRICT. Using v >= top(h) still gives a
correct multiset, but it pops and pushes on every equal value, which is pure
wasted work. It is an efficiency bug rather than a correctness one, which is
the kind that survives testing.
The second boundary is k = n, where nothing is ever evicted and the heap
simply collects everything.
## What is NOT an overflow here
Values reach 10^9 in magnitude and nothing is added or multiplied, so 32
bits are sufficient throughout. The place a 32-bit build would break is an
accumulator, and this problem has none. Problem 883, which sums the k
smallest, does.
## Related problems
Problem 272 asks for the kth largest VALUE of a fixed array, one number, by
sorting. Problem 879 asks arbitrary ranks of a fixed array and explains why a
heap is wrong there. Here the whole top k is wanted in order, which is the
smallest question for which a bounded heap is genuinely the right answer.
## Cost
Time O(n log k). Space O(k).
Constraints - `1 ≤ k ≤ n ≤ 200000` - `-1000000000 ≤ a[i] ≤ 1000000000`
Input
The first line contains two integers n and k.
The second line contains n integers.
Output
Print the k largest values in decreasing order, on one line, separated by single spaces, with duplicates repeated as many times as they occur. Print no other words.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.