1
$\begingroup$

There is popular problem:

Given that integers are read from a data stream, find the median of elements read so far in an efficient way.

One of possible solutions:

Use max-heap for left heap (i.e. for elts lower than median) and min-heap for right heap (i.e. for elts higher than median). While receiving each new integer from the stream, add it to either left heap or right heap depending on comparison with current median. Keep left and right heaps balanced, if one of heaps bigger by one, extract top element and put to another heap.

Here is a implementation of this solution.

This question is very popular in job interviews (I had that one), many people on the internet mention this algorithm (at least a few blogs/books about coding interviews).

But this algorithm looks like "noname" algorithm because nobody mentioned author of this algorithm.

I understand how this algorithm works. But I would be glad to hear academic sources about this algorithm.

Improve this question
$\endgroup$
4
  • $\begingroup$ I tried to consider edge cases: both heaps are empty, one heap has 1 element other has 0 elements, both heaps are equal in size, one of heaps is bigger by one. In each of these cases I considered a new element is being lower/equal/bigger to current median. I considered median as a whole number and as a mean of the two middle values. I.e. in total is 4*3*2 = 24 cases. I didn't stuck. But I'm curious who invented algorithm first and read from the source and compare my current understanding. It looks like it's a noname algorithm, but I believe that somebody in the past discovered this algorithm. $\endgroup$
    – uintptr_t
    Commented Jul 25, 2015 at 19:42
  • $\begingroup$ This has "exercise problem" flavor (and hardness), so there may not be an academic reference. But then, some things that required several articles to get right some decades ago are exercise problems today, so there may as well be one. $\endgroup$
    – Raphael
    Commented Jul 26, 2015 at 16:35
  • $\begingroup$ @Raphael It is often the case that a problem is hard when not one has any idea of the answer, and much easier once it is know that someone has the solution. The firing squad problem was open for two years, and was solved in a few hours once it was known that a solution existed. Huffman allegedly did not know he was solving an open problem, when he found Huffman coding as a solution to a take home exam (his MIT teacher had kept the information). This median problem is trivial when one is told it takes 2 heaps, and pretty much so without knowing that. But not before heap became commonplace. $\endgroup$
    – babou
    Commented Jul 26, 2015 at 16:51
  • $\begingroup$ I looked around for references, and the best I could find was this thread on SO: stackoverflow.com/questions/1387497/… and this paper of sorts: denenberg.com/omf.pdf. The latter doesn't have any references to the basic algorithm, so it's likely unpublished. $\endgroup$
    – KWillets
    Commented Jul 26, 2015 at 18:19

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.