The Median Maintenance Problem

Internal

• Heaps

Problem

Give a sequence of numbers x₁, x₂, .... x_n, report at each step i the median number among the numbers seen so far. For a given k, the and assuming that x₁, x₂, .... x_k are sorted in an ascending order, the median will be on (k + 1)/2 position if k is odd and on k/2 position is k is even.

Discussion

The problem can be resolved by repeatedly solving the selection problem on the set of numbers seen so far, but the selection problem has a running time of O(n), so repeating the selection algorithm for each number will have a running time of O(n²). The median maintenance problem is a canonical use case for a heap.

Solution

Use two heaps: a max heap H_low that supports the REMOVE-MAX operation with O(1) running time and a min heap H_high that supports the REMOVE-MIN operation, also with O(1) running time.

The idea is to maintain the first smallest half elements in H_low and the largest half of the elements in H_high.

Every time a new element arrives, it will be inserted in H_low.

While processing an element with an odd index, H_low contains (k + 1)/2 elements and H_high contains (k-1)/2 elements. The median, which according to the definition, is the (k + 1)/2 element in the sequence of sorted k elements, is at the top of the H_low heap and can be retrieved with the MAXIMUM() operation.

While processing an element with an even index, H_low contains immediately after insertion a larger number of elements than it should, so both heaps should be rebalanced by extracting the maximum element from H_low with REMOVE-MAX() and inserting it in H_high with INSERT(). After the sequence of operations is complete, H_low and H_high will both contain the same number of elements k/2. The current median will still be at the top of H_low and can be retrieved with the MAXIMUM() operation.

while there is an x element:
  if x has an odd index
    Hlow.INSERT(x)
    record running median as Hlow.MAXIMUM()
  else # x as an even index
    Hlow.INSERT(x)
    Hhigh.INSERT(Hlow.REMOVE-MAX()) # rebalance the heaps
    record running median as Hlow.MAXIMUM()

More details:

https://www.coursera.org/learn/algorithms-graphs-data-structures/lecture/iIzo8/heaps-operations-and-applications