C++ Efficiently Calculating a Running Median [duplicate]

by

The streaming median is computed using two heaps. All the numbers less than or equal to the current median are in the left heap, which is arranged so that the maximum number is at the root of the heap. All the numbers greater than or equal to the current median are in the right heap, which is arranged so that the minimum number is at the root of the heap. Note that numbers equal to the current median can be in either heap. The count of numbers in the two heaps never differs by more than 1.

When the process begins the two heaps are initially empty. The first number in the input sequence is added to one of the heaps, it doesn’t matter which, and returned as the first streaming median. The second number in the input sequence is then added to the other heap, if the root of the right heap is less than the root of the left heap the two heaps are swapped, and the average of the two numbers is returned as the second streaming median.

Then the main algorithm begins. Each subsequent number in the input sequence is compared to the current median, and added to the left heap if it is less than the current median or to the right heap if it is greater than the current median; if the input number is equal to the current median, it is added to whichever heap has the smaller count, or to either heap arbitrarily if they have the same count. If that causes the counts of the two heaps to differ by more than 1, the root of the larger heap is removed and inserted in the smaller heap. Then the current median is computed as the root of the larger heap, if they differ in count, or the average of the roots of the two heaps, if they are the same size.

Code in Scheme and Python is available at my blog.

More Related Contents:

  1. What is the right approach when using STL container for median calculation?
  2. Insertion sort stops working after million input
  3. How to find out how many bits are set (equal 1) in the product of two integers [closed]
  4. C++ – Find numbers between first and last negative numbers in Array
  5. Absolute Distinct Numbers
  6. Image Processing: Algorithm Improvement for ‘Coca-Cola Can’ Recognition
  7. Calculating pow(a,b) mod n
  8. Rotating a point about another point (2D)
  9. Create Random Number Sequence with No Repeats
  10. Fast ceiling of an integer division in C / C++
  11. Getting the actual length of a UTF-8 encoded std::string?
  12. Search for a struct item in a vector by member data
  13. How can I find the actual path found by BFS?
  14. Splitting a string by a character
  15. what is the difference between set and unordered_set in C++?
  16. Similar String algorithm
  17. Calculating the Amount of Combinations
  18. Searching in a sorted and rotated array
  19. Better shading on BW display while rendering filled surfaces
  20. `std::list::sort()` – why the sudden switch to top-down strategy?
  21. How can I sort an STL map by value?
  22. Algorithm to add or subtract days from a date?
  23. Easiest way of using min priority queue with key update in C++
  24. Creating N nested for-loops
  25. Edges on polygon outlines not always correct
  26. What’s time complexity of this algorithm for finding all combinations?
  27. How to find and replace all occurrences of a substring in a string?
  28. Counting number of bits: How does this line work ? n=n&(n-1); [duplicate]
  29. Good C++ solutions to the “Bring all the zeros to the back of the array” interview challenge
  30. Order Statistic Tree in C++

Leave a Comment