Streaming Scenarios

In streaming settings, data arrives one element at a time and you must maintain a statistic (e.g. top K, median) without storing the entire stream. Heaps are the standard tool. See [Top K Problems](/blog/algorithms/heap-top-k/top-k-problems) for the fixed-array pattern and [Heap Fundamentals](/blog/algorithms/heap-top-k/heap-fundamentals) for operations and complexity.

Top K in a Stream

Problem: Process a stream of numbers; at any time, support “return the current top K largest.”

Solution: Keep a min-heap of size K. For each new value: if heap size < K, add it; else if the value is greater than the heap’s minimum, poll the min and add the new value. The heap always holds the current top K; the root is the K-th largest.

Space O(K); per-element time O(log K).

Running Median

Problem: After each new element, report the median of all elements seen so far.

Solution: Maintain two heaps:

• A max-heap for the lower half (so its top is the max of the lower half).
• A min-heap for the upper half (its top is the min of the upper half). Keep the sizes balanced (differ by at most 1). After each insert, rebalance if needed. Median is the max-heap top (if lower half has one more) or the average of both tops (if equal size).

Insert: O(log n); median: O(1). Space O(n).

Summary

• Top K in stream: One min-heap of size K; evict minimum when adding a larger element.
• Running median: Max-heap (lower half) + min-heap (upper half), keep balanced; median from heap tops. Both are standard interview patterns for streaming data.