Top-K with a Heap

Find the K largest elements in a stream of N items, K << N.

Naive: sort all, take last K. O(N log N) time, O(N) memory.

Better: maintain a min-heap of size K.

For each new element: if heap not full, push. Else if it's bigger than the min (root), replace.

Time: O(N log K). Memory: O(K).

For a billion items and K=100, this is 1e9 * log(100) ≈ 7e9 operations vs 3e10 for full sort. Faster + far less memory.

Used in: search result top-K, recommendation systems, percentile estimation.

Selection algorithms (Quickselect) give O(N) average for top-K but require all data in memory. The heap approach is streaming-friendly.