efficient running median

[Raymond Hettinger]

On Oct 13, 11:57 am, sturlamolden <sturlamol... at yahoo.no> wrote:
> On 13 Okt, 18:33, Paul Rubin <http://phr...@NOSPAM.invalid> wrote:
>
> > The obvious way to compute a running median involves a tree structure
> > so you can quickly insert and delete elements, and find the median.
> > That would be asymtotically O(n log n) but messy to implement.
>
> QuickSelect will find the median in O(log n) time.

Right.  See http://code.activestate.com/recipes/269554/ for a sample
implementation in Python.


Raymond