You built something elegant in the last screen. Two heaps — a max-heap holding the small half, a min-heap holding the large half — and the median always sitting right at the boundary between them. Every insertion is O(log n). Every median query is O(1). The sorted-array bottleneck is gone.

But you built it under ideal conditions. The numbers arrived in a cooperative order, and the two heaps stayed roughly the same size. What happens when the stream is not so kind?

Imagine ten numbers arrive, and nine of them are small. They all flow into the max-heap — because each one is less than or equal to the max-heap's root. The min-heap sits nearly empty, holding just one lonely element. The max-heap's root — the largest of the “small half” — is supposed to represent the median. But the “small half” now contains nine out of ten numbers. The boundary has drifted so far that the root of the max-heap is nowhere near the true middle. Your machine is structurally perfect — every heap property holds — and yet it is lying to you.

The problem has a precise name: the balance invariant. For the two-heap structure to produce correct medians, the heaps must differ in size by at most one element. If the total count is even, each heap holds exactly half. If odd, one heap holds one extra — and its root alone is the median.

Why exactly one? Because the median is defined by position: the middle element when all values are sorted. The max-heap root represents position maxHeap.size in sorted order, and the min-heap root represents position maxHeap.size + 1. Those positions only correspond to the median when maxHeap.size equals minHeap.size (or differs by one). If one heap has k more elements than the other, the boundary shifts by k positions away from the true middle — and the roots represent elements that are nowhere near the center.

This is not a suggestion or a performance optimization. It is a correctness requirement. Break the invariant, and the structure does not return a slightly-wrong median. It returns a completely wrong one — a value that might not even be close to the true answer. The heaps are valid. The roots are accessible. The O(1) query completes instantly. But the answer is garbage, and nothing about the data structure's shape tells you it has failed. The corruption is silent.

Let's make the failure concrete. Say you have inserted the numbers 1, 2, 3, 4, 5 — and suppose, through unfortunate routing, the max-heap ends up with [1, 2, 3, 4] while the min-heap holds only [5]. Both heaps are valid: 4 is the largest in the max-heap, 5 is the smallest in the min-heap. The heap property is intact everywhere.

But the median of [1, 2, 3, 4, 5] is 3 — the element at position 3 in sorted order. Your max-heap's root says 4. Your min-heap's root says 5. Neither root is the median. The boundary sits between position 4 and position 5, not at position 3 where it belongs. You are off by two positions, and the error will only grow as more elements pile onto the heavy side.

Try piling elements onto one side and watch the seesaw tilt. The moment the difference exceeds one, the median is wrong.

The insidious part: the structure looks healthy. If you inspect the two heaps, they each satisfy the heap property. The roots are well-defined. The only visible clue is the size mismatch — 4 vs 1 — and if you are not checking sizes, you will never notice. You will confidently return the wrong answer, over and over, with no error and no warning.

Words can describe the failure. What follows will make you feel it.

Below is your two-heap machine from the previous screens — except it has been sabotaged. The rebalancing logic has been quietly disabled. Numbers will arrive one at a time. Your job is to predict which heap each number belongs to and insert it. Everything will look fine at first. The heaps will accept the elements, the roots will update, and the structure will appear to be working.

Then you will check the median. And something will be very wrong.

The sizes drifted to 6 vs 4. The balance invariant is broken. Every heap property still holds — the structure looks fine — but the median is silently wrong. Watch what the corruption looks like from the outside.

The max-heap has too many elements. The fix is surgical: extract the root of the overweight heap and insert it into the other side. One operation to shrink the heavy side, one to grow the light side. The boundary shifts by exactly one position.

Tap the root of the max-heap to begin the transfer. Then verify the median is correct again by selecting both roots.

You fixed the imbalance once. Now see if the fix holds under a stream of new arrivals. Three more numbers will arrive in rapid succession. After each insertion, predict whether a rebalance is needed.

Every rebalance you just witnessed followed the same pattern. But how expensive was each one?

You have felt the fix. You have predicted when it triggers. Now construct the function that enforces the balance invariant automatically.

The fix is almost disappointingly simple. When one heap grows larger than the other by more than one element, you extract the root of the bigger heap and insert it into the smaller one. That is the entire rebalancing algorithm. One extractMax (or extractMin) followed by one insert. Two heap operations, each O(log n), for a total cost of O(log n).

Think about which element moves. The root of the max-heap is the largest value in the small half — the element closest to the boundary from the left. The root of the min-heap is the smallest value in the large half — the element closest to the boundary from the right. When you extract one and insert it into the other side, you are shifting the dividing line by exactly one position. The element that was “too big for the small side” becomes “the smallest thing on the large side,” which is exactly where the sorted order says it belongs.

The critical discipline is when this happens: after every single insertion. Not eventually. Not periodically. Not “when the imbalance gets bad enough to notice.” Every time a new element enters either heap, you compare maxHeap.size and minHeap.size. If the difference exceeds one, you rebalance. The invariant must hold at every step, because any step could be the one where someone asks for the median. A single missed rebalance is a single wrong answer — and in a streaming system, you may never know it happened.

Take stock of what you now have. The addNum operation does three things in sequence: route the new value to the correct heap (O(1) comparison + O(log n) insertion), check the balance (O(1) size comparison), and rebalance if needed (O(log n) extract + O(log n) insert). The worst case is O(log n) + O(log n) — still O(log n) overall. And the rebalance does not always trigger. When elements happen to alternate sides evenly, the heaps stay balanced on their own and the check is a free no-op.

The findMedian operation is unchanged: read one root (odd total) or average two roots (even total) — O(1) in all cases. No scanning, no shifting, no sorting. The two roots are always the two elements that straddle the median position, guaranteed by the balance invariant you just learned to enforce.

This is the complete streaming median: two heaps, a routing rule, and a balance invariant enforced after every insertion. Three ideas, each simple in isolation, combining into a structure that answers a hard question in logarithmic time. But the story is not over. So far, elements only arrive — they join the stream and stay forever. The next screen introduces a world where elements also leave. And that departure will break something you did not expect.