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 and a min heap H_high that supports the REMOVE-MIN operation.

Maintain the first smallest half elements in H_low and the largest half of the elements in H_high. When a new element comes, if its smaller than the current median insert it in H_low, if it is higher than the current median, insert it in H_high. Keep track of heap sizes and rebalance when necessary, so the total number of elements is evenly split among the heaps.

More details:

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