How do you find the top-K elements from a large stream efficiently?

“How do you find the top-K elements from a large stream efficiently?”

For top-K largest, use a min-heap of size K: the smallest of your current best-K sits at the top, ready to be evicted the moment something larger arrives.

PriorityQueue<Integer> heap = new PriorityQueue<>(); // min-heap
for (int x : stream) {
    heap.offer(x);
    if (heap.size() > k) heap.poll(); // drop smallest
}
// heap now holds the k largest

k largest elements

Time:

O(n log k)

Space:

O(k)

Top-N dashboards (highest-value orders, slowest endpoints, top customers) over huge datasets use a bounded heap so you never load or sort the whole dataset in memory.

Keywords they're listening for:

• ✓ min-heap of size K
• ✓ O(n log k) vs O(n log n)
• ✓ O(k) space
• ✓ bounded memory

• ✗Sorting the entire dataset to take K
• ✗Using a max-heap of all n elements (O(n) space)
• ✗Wrong heap direction (min vs max)

• ✓Bound the heap to K for streaming top-K
• ✓Use a Comparator for domain objects
• ✓Consider QuickSelect for one-shot in-memory top-K

1. 1How does the heap-based approach compare to full sort or QuickSelect?
2. 2How would you parallelize top-K across shards?
3. 3What Comparator do you use for top-K by a custom field?

• PriorityQueue
• Comparator
• QuickSelect
• Stream