Two Heaps: The Balance Scale
A running median from a max-heap and min-heap kept in balance.
The median is the middle value of everything seen so far. Sorting on every arrival costs O(n log n) each time; this structure answers in O(1) after O(log n) per insert.
The idea: split the numbers into two halves. A max-heap holds the smaller half, so its root is the largest of the small numbers. A min-heap holds the larger half, so its root is the smallest of the big numbers. The median always lives at the roots: if the sizes are equal, average the two roots; if one side is bigger by one, its root is the median.
Two invariants keep this true: every value in the left pan is less than or equal to every value in the right pan, and the sizes never differ by more than one.
What to watch for:
- Each arriving number drops into the left (max-heap) pan first, then the left root immediately transfers across the beam. This push-through step is what enforces the ordering between the pans — skipping it is the classic bug.
- The beam re-levels whenever one pan gets two ahead: the overloaded pan's root hops across.
- The median bubble between the apexes updates after every arrival, without any sorting happening anywhere.