You need the $100$ largest values from a stream of $10^9$ numbers you cannot store. What do you use?

Answer: B – A min-heap of size 100

Keep a min-heap capped at $100$. For each new value, compare it with the heap’s root, which is the smallest of the current best hundred; discard it if it is smaller, otherwise pop the root and push the new value. That is $O(\log k)$ per element and $O(n\log k)$ overall, in $O(k)$ space, on a single pass. The counter-intuitive part is that you want a min-heap to find maxima, because the element you need cheap access to is the weakest survivor. Sorting or holding every value needs $O(n)$ space, which the premise forbids.

• A. You cannot store the stream, and sorting would be $O(n\log n)$ with $O(n)$ space.
• B. Correct: $O(n\log k)$ time and $O(k)$ space, and it works on a single pass.
• C. That is $O(n)$ space, which the premise rules out.
• D. Frequency is not the question, and it is still linear space.

Takeaway: A size-$k$ heap gives the top $k$ of a stream in $O(n\log k)$.