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 those number seen so far.