The Median Maintenance Problem: Difference between revisions
| Line 2: | Line 2: | ||
* [[Heap#Canonical_Uses_of_a_Heap|Heaps]] | * [[Heap#Canonical_Uses_of_a_Heap|Heaps]] | ||
=Problem= | =Problem= | ||
Give a sequence of numbers x<sub>1</sub>, x<sub>2</sub>, .... x<sub>n</sub>, report at each step i the median number among the numbers seen so far. | Give a sequence of numbers x<sub>1</sub>, x<sub>2</sub>, .... x<sub>n</sub>, report at each step i the median number among the numbers seen so far. For a given k, the and assuming that x<sub>1</sub>, x<sub>2</sub>, .... x<sub>k</sub> 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= | =Discussion= | ||
Revision as of 22:49, 13 October 2021
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 and a min heap Hhigh that supports the REMOVE-MIN operation.
Maintain the first smallest half elements in Hlow and the largest half of the elements in Hhigh. When a new element comes, if its smaller than the current median insert it in Hlow, if it is higher than the current median, insert it in Hhigh. Keep track of heap sizes and rebalance when necessary, so the total number of elements is evenly split among the heaps.
More details: