The running median
As numbers stream in, you must report the median of everything seen so far at any moment. Re sorting on each query is wasteful, so a pair of heaps keeps the answer ready.
Two heaps facing each other
Split the values into a lower half and an upper half.
- A max heap holds the smaller half, so its top is the largest of the low values.
- A min heap holds the larger half, so its top is the smallest of the high values.
The two heap tops straddle the middle, which is exactly where the median lives.
Insert and rebalance
When a new value arrives, push it into the appropriate heap by comparing against the current tops. Then rebalance so the heap sizes differ by at most one, moving a top across if needed.
- If sizes are equal, the median is the average of the two tops.
- If one is larger, its top is the median.
Each insert touches only heap tops and a single shift, so updates are cheap.
Key idea
The streaming median keeps a max heap of the low half and a min heap of the high half, rebalancing after each insert so the median is always read directly from the heap tops in logarithmic update time.