template<typename T, typename Compare = std::less<T>>
class RunningMedian< T, Compare >
For use in the efficient computation of a running median.
There are quite a few different approaches to this problem, including
1) O(sqrtN) algorithm by Soumya D. Mohanty
2) O(logN) algorithm based on an indexable skiplist by Raymond Hettinger
3) O(logN) algorithm based on std::multiset (TopCoder Match Editorial)
The last of these is quite clever, and requires very little coding.
This implementation is based on the example from the TopCoder web-site
http://community.topcoder.com/tc?module=Static&d1=match_editorials&d2=srm310 (accessed on 20 April 2012)