Tracking a moving median
To report the median of a stream that keeps growing, you want fast access to the middle value after each new number. Sorting repeatedly is too slow. The two heaps pattern splits the data into a lower half and an upper half, each kept in a heap so the boundary values are always reachable.
The two halves
- A max heap holds the smaller half, so its top is the largest of the small numbers.
- A min heap holds the larger half, so its top is the smallest of the large numbers.
The median sits at the boundary between these tops. When the counts are equal, the median is the average of the two tops. When one heap holds one extra element, that heap's top is the median.
Inserting and rebalancing
For each new value you push it into one heap, then rebalance so the sizes differ by at most one and every small element stays below every large one. Rebalancing means moving a top from one heap to the other when needed. Each insertion does a constant number of heap operations.
Key idea
Split the stream into a low max heap and a high min heap, keep them balanced, and read the median straight off the two heap tops.