What is the two heaps pattern, and which problems does it solve?
The two heaps pattern is the technique of keeping two heaps, one for the smaller half of the values and one for the bigger half, with the rule that the two heaps are always the same size or the lower one is one bigger.
the heap what it holds the property
-------------- --------------------- -----------------------
the lower heap the smaller half its top is the biggest
of the lower half
the upper heap the bigger half its top is the smallest
of the upper half
And which problems does it solve? Here are the main ones.
the problem what the pattern gives you
------------------------------ ---------------------------------
the median of a stream the middle value
the kth smallest of a stream the top of the lower heap
the kth largest of a stream the top of the upper heap
a running average and median both at once
And the reason it works is the balance between the two heaps. The lower heap is a max heap, so the biggest of the lower half is at its front and you can take it out quickly. The upper heap is a min heap, so the smallest of the upper half is at its front. And because the lower heap is never smaller than the upper heap, every value in the lower half is less than every value in the upper half.
And the two rules that keep it balanced are these. When you add a value, you put it in the upper heap and then you move the top of the upper heap down into the lower heap, so the lower half is always at least as big. And when the lower heap has more than one extra item, you move the top of the lower heap up into the upper heap, so the two heaps stay within one of each other in size.
after adding a value
the lower heap has the same number as the upper heap, or one more
and every value in the lower heap is less than every value in the upper heap
And the complexity is O of log n for each add, and O of 1 to look at the top of either heap.
So the rule to remember is this. Two heaps, the lower one a max heap and the upper one a min heap, and they are always in balance.
The next two questions in this topic show the median and the top k frequent elements.