Median for a stream of numbers

Given a stream find its median

Solution

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.

Show your support

Clapping shows how much you appreciated Nitish Chandra’s story.