Introduction to Two Heaps Pattern

Numbers arrive one at a time. After each new number, report the median of everything seen so far.

5        median 5
5 15     median 10
5 15 1   median 5

Sorting after every arrival gives the right answer and costs O(N log N) each time. Keeping a sorted list is better, but inserting into the middle still shifts everything after it, which is O(N) per number.

Look at what the median actually needs. It needs the largest of the small half and the smallest of the large half. Nothing else. The order inside each half is irrelevant.