Introduction to Two Heaps Pattern

Numbers arrive one at a time. After each number arrives, report the median of all numbers seen so far.

5          median = 5
5, 15      median = 10
5, 15, 1   median = 5

The median is the middle value after sorting.

Sorting all numbers after every insertion is expensive. Keeping a sorted array still requires moving many values during insertion.

The median needs only two values:

• the largest value in the lower half
• the smallest value in the upper half

A max heap gives the largest value in a group. A min heap gives the smallest value.