Tracks the overall median of a stream of values "on-line" in reasonably efficient fashion.
MedianTracker supports efficient median queries on and dynamic additions to a list of values. It provides both the lower and upper median of all values seen so far. Any __cmp__()-able object can be tracked, in addition to numeric types. add() takes log(n) time for a tracker with n items; lower_median() and upper_median() run in constant time. Since all values must be stored, memory usage is proportional to the number of values added (O(n)).
released on 2 September 2009
|License||Verified by||Verified on||Notes|
|Expat||Kelly Hopkins||24 February 2010|
Leaders and contributors
Resources and communication
This entry (in part or in whole) was last reviewed on 24 February 2010.