# The Median Maintenance Problem

# Internal

# Problem

Give a sequence of numbers x_{1}, x_{2}, .... 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_{1}, x_{2}, .... 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^{2}). 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 H_{low}is empty || x ≤ H_{low}.MAXIMUM() H_{low}.INSERT(x) else H_{high}.INSERT(x) REBALANCE(H_{low}, H_{high}) record running median as H_{low}.MAXIMUM()

REBALANCE(H_{low}, H_{high}) { # Because we're rebalancing at each step and we are maintaining the halves either equal, # or H_{low}larger than H_{high}with one element the difference in size can only be 2, 1, 0 or -1 difference = H_{low}.SIZE() - H_{high}.SIZE() if difference == 2 # Shift H_{low}maximum element to H_{high}H_{high}.INSERT(H_{low}.REMOVE-MAX()) else if difference == 1 || difference == 0 # Balanced, nothing to do else if difference == -1 # Shift H_{high}minimum element to H_{low}H_{low}.INSERT(H_{high}.REMOVE-MIN()) else # We're not supposed to be in this situation ERROR() }

More details: