What is the best way to keep track of the median?
- by Steven Mou
I read a question in one book: Numbers are randomly generated and stored into an (expanding) array, How would you keep track of the median?
There are two data structures can solve the problem. One is the balanced binary tree, the other is two heaps which keep trace of the biggest half and the smallest half of the elements.
I think these two solutions has the same running time as O(n lg n), but I am not sure of my judgement.
In your opinions, What is the best way to keep track of the median?