The Median Maintenance Problem: Difference between revisions
Jump to navigation
Jump to search
| Line 4: | Line 4: | ||
The median maintenance problem is a canonical use case for a heap. | The median maintenance problem is a canonical use case for a heap. | ||
=Problem= | =Problem= | ||
Give a sequence of numbers x<sub>1</sub>, x<sub>2</sub>, .... x<sub>n</sub>, report at each step the median number of numbers seen so far. The problem can be resolved by 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<sup>2</sup>). | Give a sequence of numbers x<sub>1</sub>, x<sub>2</sub>, .... x<sub>n</sub>, report at each step the median number of numbers seen so far. | ||
=Discussion= | |||
The problem can be resolved by 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<sup>2</sup>). | |||
Revision as of 22:28, 9 October 2021
Internal
Overview
The median maintenance problem is a canonical use case for a heap.
Problem
Give a sequence of numbers x1, x2, .... xn, report at each step the median number of numbers seen so far.
Discussion
The problem can be resolved by 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).