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 and we are maintaining the halves either equal, 
  # or Hlow larger than Hhigh with one element the difference in size can only be 2, 1, 0 or -1
  difference = Hlow.SIZE() - Hhigh.SIZE()
  if difference == 2 
    # Shift Hlow maximum element to Hhigh
    Hhigh.INSERT(Hlow.REMOVE-MAX())
  else if difference == 1 || difference == 0
    # Balanced, nothing to do
  else if difference == -1
    # Shift Hhigh minimum element to Hlow
    Hlow.INSERT(Hhigh.REMOVE-MIN())
  else
    # We're not supposed to be in this situation
    ERROR()
}

More details:

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

Playground Implementation

https://github.com/ovidiuf/playground/blob/a3d3a2284f25bb81424b1e3429d38f844353197e/learning/stanford-algorithms-specialization/06-median-maintenance/src/main/java/playground/stanford/mm/Main.java#L9-L23