# What is the best way to keep track of the median?

I read a question, and I'm looking for input on how to solve it:

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 have the same running time as `O(n lg n)`, but I am not sure of my judgement.

What is the best way to keep track of the median?

### My attempt:

In this question，I think a heap is the best way to keep track of the median. There are two heaps, the big heap and the small heap, which need not to be sequential. First, we calculate the mean value of the elements in the array. If the element is less than the mean value, we put the num to the small heap. On the contrary, we put the num to the big heap. If the number of the big heap is equal to the number of the small heap, the biggest one in the small heap and the smallest one in the big heap are the median. If the two heaps have different size, we just pop the root element from the heap with bigger size and push it to the root of the smaller size heap. For big heap, the root element is the smallest one, and for small heap, the root element is the biggest one. In this way, if the two heaps have the same size or a digital difference, we find the medium in the root.

I think this solution has the running time as O(m*n), m means the times we adjust the unbalance heaps.

Is this the best way to keep track of the median?

• If you only need to track the median, the two have essentially the same complexity, but the heap-based approach will use less memory (its structure is implicit instead of requiring pointers) and generally faster as well (because it's normally stored contiguously, which will usually improve cache usage). – Jerry Coffin Jun 28 '11 at 16:06
• stackoverflow.com/questions/2579912/… would be a linear solution if you wanted one. – JB King Jun 28 '11 at 16:14
• Hehe -- `std::nth_element` anyone? – Billy ONeal Jun 28 '11 at 17:48
• This actually sounds more like a question for SO than here. – Mark B Jun 28 '11 at 19:47
• The mean value can be very deceiving to the point of being meaningless. Just imaging you have a lots of small numbers (say 1..999) and 10^8. The mean value for those 1000 numbers is ~10^5, so you end up with putting everything but 10^8 into the small heap. Therefore, the algorithm has a bad worst-case behaviour. – user281377 Jun 30 '11 at 11:49

There's probably more than 2 data structures that solve this problem. Take a look at Approximate Medians and other Quantiles in One Pass and with Limited Memory

They don't use two heaps. I imagine you could modify their algorithm to periodically get a running approximate value of median. How good an approximationwould of course, depend on many factors, not the least of which is how much data has passed through the algorithm.

A better solution is to use a skip list. Since the list into which you will be inserting is always maintained as a sorted list (by the very fact of how you are building it), the complexity of the insertion is O(log n). You will be taking advantage of the fact that the very first insertion provides you with the median at zero cost (the inserted item is the median). After each additional insertion, your list is still sorted, and the median itself will drift up or down by a single index, and this comparison is O(1).

Total complexity = O(log n)

• Total complexity for each element is `O(log n)` -- inserting n elements has a complexity of `O(n log n)` – Greg Jackson Jun 29 '11 at 16:13
• Certainly, but for a "running median," one could argue that you are inserting an unbounded set of elements, but it makes little sense to say that the complexity is O ( infinity log n ). ;-) – Michael Hays Jun 29 '11 at 16:18
• Eh... ok, my answer may not be any better than heaps. The Fibonacci heap has an insertion of O(1) and deletion of O(lg n). I've just never used it. – Michael Hays Jun 29 '11 at 16:29

In fact you can find median in O(n) operations only through finding the kth smallest number in a list, :) look into Median of Medians selection algorithm for details.

• Are you sure this can be used incrementally ? – Joey Adams Jul 17 '11 at 20:20