Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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?

————————————————————————————continue

In this question,I think the heaps 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 trace of the median?

share|improve this question
    
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
2  
stackoverflow.com/questions/2579912/… would be a linear solution if you wanted one. –  JB King Jun 28 '11 at 16:14
2  
Hehe -- std::nth_element anyone? –  Billy ONeal Jun 28 '11 at 17:48
5  
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
add comment

3 Answers 3

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.

share|improve this answer
add comment

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)

share|improve this answer
    
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
1  
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
add comment

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.

share|improve this answer
    
Are you sure this can be used incrementally ? –  Joey Adams Jul 17 '11 at 20:20
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.