efficient running median

[Paul Rubin]

sturlamolden <sturlamolden at yahoo.no> writes:
> > 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.

That makes no sense, you can't even examine the input in O(log n) time.

Anyway, the problem isn't to find the median of n elements.  It's to
find n different medians of n different sets.  You might be able to
get close to linear time though, depending on how the data acts.