Find running median from a stream of integers

by

There are a number of different solutions for finding running median from streamed data, I will briefly talk about them at the very end of the answer.

The question is about the details of the a specific solution (max heap/min heap solution), and how heap based solution works is explained below:

For the first two elements add smaller one to the maxHeap on the left, and bigger one to the minHeap on the right. Then process stream data one by one, 

Step 1: Add next item to one of the heaps

   if next item is smaller than maxHeap root add it to maxHeap,
   else add it to minHeap

Step 2: Balance the heaps (after this step heaps will be either balanced or
   one of them will contain 1 more item)

   if number of elements in one of the heaps is greater than the other by
   more than 1, remove the root element from the one containing more elements and
   add to the other one

Then at any given time you can calculate median like this:

   If the heaps contain equal amount of elements;
     median = (root of maxHeap + root of minHeap)/2
   Else
     median = root of the heap with more elements

Now I will talk about the problem in general as promised in the beginning of the answer. Finding running median from a stream of data is a tough problem, and finding an exact solution with memory constraints efficiently is probably impossible for the general case. On the other hand, if the data has some characteristics we can exploit, we can develop efficient specialized solutions. For example, if we know that the data is an integral type, then we can use counting sort, which can give you a constant memory constant time algorithm. Heap based solution is a more general solution because it can be used for other data types (doubles) as well. And finally, if the exact median is not required and an approximation is enough, you can just try to estimate a probability density function for the data and estimate median using that.

More Related Contents:

  1. Finding the median of an unsorted array
  2. How do I find the median of numbers in linear time using heaps?
  3. How can building a heap be O(n) time complexity?
  4. Heap vs Binary Search Tree (BST)
  5. How to delete in a heap data structure?
  6. “On-line” (iterator) algorithms for estimating statistical median, mode, skewness, kurtosis?
  7. Argument for O(1) average-case complexity of heap insertion
  8. How to calculate or approximate the median of a list without storing the list
  9. O(n) algorithm to find the median of n² implicit numbers
  10. O(klogk) time algorithm to find kth smallest element from a binary heap
  11. Print the biggest K elements in a given heap in O(K*log(K))?
  12. Prove that binary heap build max comparsion is (2N-2)
  13. Algorithm for merging two max heaps?
  14. Custom Weighted Scale [closed]
  15. Quicksort: Choosing the pivot
  16. How to implement a queue using two stacks?
  17. Graph auto-layout algorithm
  18. Is there an algorithm for color mixing that works like mixing real colors?
  19. Algorithm to list unique permutations of string with duplicate letters
  20. Collision detection of huge number of circles
  21. Compute rank of a combination?
  22. generate all partitions of a set [closed]
  23. Efficiently selecting a set of random elements from a linked list
  24. Find if a point is inside a convex hull for a set of points without computing the hull itself
  25. Myers diff algorithm vs Hunt–McIlroy algorithm
  26. Given Prime Number N, Compute the Next Prime?
  27. Optimized low-accuracy approximation to `rootn(x, n)`
  28. What are probabilistic data structures?
  29. How to find the number of different shortest paths between two vertices, in directed graph and with linear-time?
  30. Connected Component Labeling – Implementation

Leave a Comment