The Median Maintenance Problem: Difference between revisions
Jump to navigation
Jump to search
| Line 7: | Line 7: | ||
The problem can be resolved by repeatedly solving the [[Selection_Problem#Overview|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>). The median maintenance problem is a canonical use case for a heap. | The problem can be resolved by repeatedly solving the [[Selection_Problem#Overview|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>). The median maintenance problem is a canonical use case for a heap. | ||
=Solution= | =Solution= | ||
Use two heaps: a [[Heap#Min_Heap_and_Max_Heap|max heap]] H<sub>low</sub> that supports the <tt>[[Heap#REMOVE-MAX|REMOVE-MAX]]</tt> operation and a [[Heap#Min_Heap_and_Max_Heap|min heap]] H<sub>high</sub> that supports the <tt>[[Heap#REMOVE-MIN|REMOVE-MIN]]</tt> operation. | Use two heaps: a [[Heap#Min_Heap_and_Max_Heap|max heap]] H<sub>low</sub> that supports the <tt>[[Heap#REMOVE-MAX|REMOVE-MAX]]</tt> operation and a [[Heap#Min_Heap_and_Max_Heap|min heap]] H<sub>high</sub> that supports the <tt>[[Heap#REMOVE-MIN|REMOVE-MIN]]</tt> operation. Maintain the first smallest half elements in H<sub>low</sub> | ||
Revision as of 22:38, 9 October 2021
Internal
Problem
Give a sequence of numbers x1, x2, .... xn, 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(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