Best way to get the k largest elements from a stream of n numbers?
Options
- Sort all n numbers first: O(n log n)
- Keep a min-heap of size k: O(n log k) (Correct option)
- Push all n into a max-heap, then pop k
- Scan the numbers k times: O(nk) overall
Answer
Keep a min-heap of size k: O(n log k)
Why
A heap is a structure that always gives you its smallest item in O(1) and adds/removes in O(log size).
Keep a min-heap with the k largest numbers seen so far. For each new number, push it; if the heap has more than k items, pop the smallest.
The heap never grows past k, so the cost is O(n log k), and memory is only O(k). Python: heapq.nlargest(k, numbers).
Remember
Top k → heap of size k.