The Median Maintenance Problem

From NovaOrdis Knowledge Base
Revision as of 23:18, 13 October 2021 by Ovidiu (talk | contribs) (→‎Solution)
Jump to navigation Jump to search

Internal

Problem

Give a sequence of numbers x1, x2, .... xn, report at each step i the median number among the numbers seen so far. For a given k, the and assuming that x1, x2, .... xk 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(n2). The median maintenance problem is a canonical use case for a heap.

Solution

Use two heaps: a max heap Hlow that supports the REMOVE-MAX operation with O(1) running time and a min heap Hhigh that supports the REMOVE-MIN operation, also with O(1) running time.

The idea is to maintain the first smallest half elements in Hlow and the largest half of the elements in Hhigh.

Every time a new element arrives, it will be automatically inserted in Hlow.

While processing an element with an odd index, Hlow contains (k + 1)/2 elements and Hhigh contains (k-1)/2 elements. The median, which according to the definition, is the (k + 1)/2 element in the sequence of sorted k elements, is at the top of the Hlow heap and can be retrieved with the MAXIMUM() operation.

While processing an element with an even index, Hlow contains immediately after insertion a larger number of elements than it should, so both heaps should be rebalanced by extracting the maximum element from Hlow with REMOVE-MAX() and inserting it in Hhigh with INSERT(). After the sequence of operations is complete, Hlow and Hhigh will both contain the same number of elements k/2. The current median will still be at the top of Hlow and can be retrieved with the MAXIMUM() operation.

while each x:
  Hlow.INSERT(x)
  if x has an even odd index
    # rebalance the heaps
    Hhigh.INSERT(Hlow.REMOVE-MAX())
  record running median as Hlow.MAXIMUM()

More details:

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

Playground Implementation