The Median Maintenance Problem

Internal

• Heaps

Overview

The median maintenance problem is a canonical use case for a heap.

Problem

Give a sequence of numbers x₁, x₂, .... x_n, 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²).