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.

This is implemented by appropriately inserting each new element in the corresponding heap, and then rebalancing the heaps so H_low and H_high have the same number of elements, or H_low has with at most 1 element more than H_high. Rebalancing means extracting the top of the heap from the oversized heap and inserting the element in the other heap.

Maintaining this load for both heaps makes possible to read the current median, at any moment, as the top of H_low.

while each x:
  if Hlow is empty || x ≤ Hlow.MAXIMUM()
    Hlow.INSERT(x)
  else
    Hhigh.INSERT(x)
  REBALANCE(Hlow, Hhigh)
  record running median as Hlow.MAXIMUM()

REBALANCE(Hlow, Hhigh) {
  # Because we're rebalancing at each step, the difference in size will never be larger than 2
}

More details:

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