MedianTracker. Kleint, J. In Free Software Directory. Free Software Foundation.
MedianTracker [link]Paper  abstract   bibtex   
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)).
@incollection{kleintMedianTracker2011,
  title = {{{MedianTracker}}},
  booktitle = {Free {{Software Directory}}},
  author = {Kleint, John},
  date = {2011-04},
  publisher = {{Free Software Foundation}},
  location = {{Boston, USA}},
  url = {http://mediantracker.sourceforge.net/},
  abstract = {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)).},
  keywords = {*imported-from-citeulike-INRMM,~INRMM-MiD:c-12643666,command-line,expat,free-scientific-software,free-software,free-software-directory,mathematics,statistics}
}
Downloads: 0