Finding continuous median

Question

How would you compute the medians for a given input that updates every time a new input is added? For example:

• 1 - Median is 1
• 1,2 - Median is 3/2
• 1,2,3 - Median is 2

Answer 1

You can do it in O(logn) per element.

Build AVL tree (or RBT), set one pointer to median. And now augment AVL with full threads (both), parent pointer.
Insert time is logarithmic, successor and predecessor is constant operation, thus updating median pointer is constant time operation.

Parent pointer plus threads might seem redundant, but this guarantees no traversal, median update is done in rotation phase.

Pros: only insertion time matters. Structure is dynamic, no need to reallocate array or move elements.

Cons: there is overhead in space and allocating nodes.

Answer 2

I don't see how it can be done in less than O(n) time.

You will have to keep a sorted list of present items. Whenever a new item arrives, you will have to insert it in the correct position. This will require O(n) time.

Calculating the new median is then elementary. If new N is odd, then it is array[(N-1)/2], else it is ( array[(N)/2] + array[(N)/2 - 1] ) / 2.