Possible Duplicate:
Rolling median algorithm in C
Given that integers are read from a data stream. Find median of elements read so far in efficient way.
Solution I have read: We can use a max heap on left side to represent elements that are less than the effective median, and a min heap on right side to represent elements that are greater than the effective median.
After processing an incoming element, the number of elements in heaps differ at most by 1 element. When both heaps contain the same number of elements, we find the average of heap’s root data as effective median. When the heaps are not balanced, we select the effective median from the root of heap containing more elements.
But how would we construct a max heap and min heap i.e. how would we know the effective median here? I think that we would insert 1 element in max-heap and then the next 1 element in min-heap, and so on for all the elements. Correct me If I am wrong here.