Keeping the middle in reach
Some problems need the median of a growing stream, or the balance point between a smaller and a larger group. Re sorting after every insert is wasteful. The two heaps pattern keeps the data split into two halves so the boundary value is always one peek away.
A max heap meets a min heap
Maintain two heaps facing each other.
- A max heap holds the smaller half, with the largest of that half on top.
- A min heap holds the larger half, with the smallest of that half on top.
- After each insertion, rebalance so the heaps differ in size by at most one.
The two tops straddle the middle of all values. The median is either the top of the larger heap or the average of both tops when sizes are equal.
Rebalancing on insert
Each new value goes into the appropriate heap based on the current tops, then if one heap grows too large you move its top across to the other. This handoff keeps both halves nearly equal so the median stays readable at all times.
Key idea
Hold the lower half in a max heap and the upper half in a min heap, rebalancing on each insert so the median is always available from the two tops.