Return to Question

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 intuitively how this algorithm works. But I would be glad to hear academic sources about this algorithm with rigorous proof of correctness.

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.

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 intuitively how this algorithm works. But I would be glad to hear academic sources about this algorithm and rigorous proof of correctness.

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 intuitively how this algorithm works. But I would be glad to hear academic sources about this algorithm with rigorous proof of correctness.