Median for a stream of numbers
Given a stream find its median
We will divide all the numbers we get into two parts of almost equal length . that means if the first part contains k numbers the second part should either contain k or k + 1 number
This will be our invariant.We will always keep the length of the second list 1 greater or equal to the first list
We will maintain two heaps one a max heap of first part that means the root of this heap will be greater than or equal to all the other elements and the other a min heap which will contain the reverse. This also will be our invariant
The third invariant is that all elements in first list should be smaller than or equal to the elements in the second list
Now when we see a new number and the length of the first list and the second list are same we want to add it to the second list to keep our first invariant but we also need to maintain invariant two . So lets add the number to the first list and then extract the maximum of the first list . Now add this number to the second list. Note that we cannot simply add the element to the second list because our element can be smaller than the root of the first list. Adding it would destroying the order that all elements of the first list should be smaller or equal than all elements of second list.
now when the length of second list is greater than of the first list we want to add to the first list. In this case also if we add willy nilly it can lead to violation of invariant 3. What we need to do is add the number to the second list extract the minimum and then add that number to the first list.