The Median Maintenance Problem

Internal

• Heaps

Problem

Give a sequence of numbers x₁, x₂, .... x_n, report at each step the median number of numbers seen so far, at each step i.

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