Search code examples
algorithmmedian

finding running medium from a stream

Problem: Given that integers are read from a data stream. Find median of elements read so far in efficient way.

I found a solution here

My questions is why do we need to use heaps instead of just simply adding numbers into a vector?

For example, assuming we are using a vector to store the incoming data, then we call the method to calculate the median as follows:

if vector size is even
   return (element at size/2 + element at size/2-1);
else
   return (element at size/2);

Would the above solution work?

Solution

  • Your solution cannot work if the elements are not in order in your vector. And if you add elements at the end of the vector, they will not be in order.

    On the other hand, the elements are in order in a heap.

    Also, there is a missing division by two in the first return statement.