Streaming median

[kasia-kobalczyk]

Implement streaming median (with an optional window).

[THargreaves]

I assume this will be an approximate median? Or at the very least have the option to be.

Exact median requires all previous values to be stored (although you can stream so that it's computed in only one pass), which would make it unusable in big data contexts.

[kasia-kobalczyk]

Streaming median can be efficiently calculated with two heaps: left heap with the largest element on top, right heap with the smallest element on top; the median is then just the average of the two top values (in case when n even) or one of the two top values (in case when n is odd).

But sure, this is an exact solution which requires O(n) memory. So for big data an approximate method should be used.