In a two-heap running median, what invariant holds after every insert, and how is it restored?
answer
- Two conditions, not one
- One is about values, one about counts
- How far apart may the sizes drift?
- An insert can overshoot by only one
- One pop-and-push changes the gap by two
basics
~20 sEvery value in the max-heap is at most every value in the min-heap, and the two sizes differ by at most one. A single pop-and-push, moving one top from the heavier heap to the lighter one, restores the size part after any insert.
solid answer
~50 sTwo things must hold after each sample is absorbed. The **ordering** part: everything in the lower max-heap is `<=` everything in the upper min-heap, which is what makes the tops the middle values. The **size** part: the counts differ by at most one, by convention with the lower heap carrying the extra, which is what makes the median readable from the tops alone. Routing keeps ordering true — compare the new sample against the max-heap's top and push it into the half it belongs to. That push can break the size part by one, so you follow it with at most one repair move: if the lower heap is now two ahead, pop its top into the upper heap; if the upper heap is ahead at all, pop its top into the lower heap. One move always suffices because a single insert changes one count by exactly one, so the imbalance can only overshoot by one.
code
pseudocode · 15 lines// lower: max-heap of the small half upper: min-heap of the large half
insert(x):
if isEmpty(lower) or x <= top(lower):
push(lower, x)
else:
push(upper, x)
if size(lower) > size(upper) + 1:
push(upper, pop(lower))
else if size(upper) > size(lower):
push(lower, pop(upper))
median():
if size(lower) > size(upper):
return top(lower)
return (top(lower) + top(upper)) / 2go deeper
Be able to state both conditions in one breath: ordering between the halves, sizes differing by at most one. Know that the new sample is routed by comparing it against the max-heap's top.
Explain the repair moves in both directions and argue why exactly one move is enough after a single insert. Trace a short stream out loud, including the handoff when the count turns odd.
Show how you would assert the invariant after every insert and property-test against a brute-force reference, since a broken invariant produces a plausible wrong number instead of a failure.
Frame the invariant as the contract other code depends on, and decide where it is enforced — assertions in a hot path, a debug-only check, or a fuzz test in the build — given the cost of a silently wrong percentile.
## The two halves of the invariant The structure is a max-heap `lower` holding the smaller samples and a min-heap `upper` holding the larger ones. Two conditions must be true whenever the median is read: 1. **Ordering:** `top(lower) <= top(upper)`, and more strongly every element of `lower` is `<=` every element of `upper`. This is what makes the tops the two values straddling the middle. 2. **Size:** `size(lower) - size(upper)` is either `0` or `1`. This is what lets the read be a fixed formula rather than a search. The read depends on both. If sizes are equal, the median is the mean of the tops; if `lower` is one ahead, the median is `top(lower)`. Break either condition and the formula silently returns a value that is not the median — no crash, no exception, just a wrong number on the dashboard. ## Restoring it in two steps **Step one, routing, preserves ordering.** A new latency sample `x` goes into `lower` when `lower` is empty or `x <= top(lower)`; otherwise it goes into `upper`. If `x <= top(lower)` then `x` is at most the largest small value and therefore at most every upper value, so it belongs below. Otherwise `x` is greater than every element of `lower`, so putting it above is safe. **Step two, rebalancing, restores size.** The push just made one heap one element heavier, so exactly one of three states holds: still balanced, `lower` two ahead, or `upper` one ahead. Two repair rules cover the last two, and each is a single pop from one heap and a push into the other. It matters that both directions are implemented; repairing only one is the classic silent bug. Why one move is always enough: each insert changes exactly one size by exactly one, so if the invariant held before, it can be violated by at most one element after. Moving one element changes the difference by two, which is precisely enough to step from an out-of-range difference back into range. The move is also ordering-safe — the top of `lower` is the largest small value, so it is the correct element to promote, and the top of `upper` is the smallest large value, so it is the correct one to demote. ## A trace on a latency stream Samples in milliseconds, arriving in this order: 12.0, 40.5, 7.2, 31.0, 9.9, 55.4, then 22.3. | arrives | lower (max-heap) | upper (min-heap) | repair | median | |---|---|---|---|---| | 12.0 | {12.0} | {} | none | 12.0 | | 40.5 | {12.0} | {40.5} | none | 26.25 | | 7.2 | {7.2, 12.0} | {40.5} | none | 12.0 | | 31.0 | {7.2, 12.0} | {31.0, 40.5} | none | 21.5 | | 9.9 | {7.2, 9.9, 12.0} | {31.0, 40.5} | none | 12.0 | | 55.4 | {7.2, 9.9, 12.0} | {31.0, 40.5, 55.4} | none | 21.5 | | 22.3 | {7.2, 9.9, 12.0, 22.3} | {31.0, 40.5, 55.4} | move 22.3 up-to-down | 22.3 | The seventh sample is the interesting one. 22.3 is greater than `top(lower) = 12.0`, so routing sends it to `upper`, making `upper` one ahead. The repair pops `top(upper)` — which is now 22.3 itself, since it is the smallest large value — and pushes it into `lower`, whose top becomes 22.3. Sorting all seven values by hand gives 7.2, 9.9, 12.0, **22.3**, 31.0, 40.5, 55.4, so the structure agrees. Note that the element promoted across the boundary was the one just inserted; that is a coincidence of this stream, not a rule. ## Ties and duplicate-heavy streams A latency stream where 90% of samples are the same rounded value is a common shape, and it worries people who think the invariant is about values. It is not: the size condition counts elements, and equal values may be spread across both heaps freely, because the ordering condition uses `<=` and is satisfied when `top(lower) == top(upper)`. Whether ties route down (`x <= top(lower)`) or up (`x < top(lower)`) changes only which half a tie lands in; the rebalance step corrects the resulting size difference either way, and the median is the same number regardless, because the elements involved are indistinguishable. What does change is the shape of the heaps: with strict `<` routing, a long run of equal values all lands in `upper` and every second insert triggers a repair move. Correct, but twice the moves — a small constant, and a reason to prefer the `<=` form. ## Testing the invariant rather than the output Because a violated invariant produces a plausible-looking number, the check worth writing is not "is the median right for this fixture" but an assertion after every insert: the size difference is in range, and `top(lower) <= top(upper)`. Paired with a random stream and a brute-force sorted reference, that catches routing and rebalance errors on the first few samples rather than in production.
- A stream where 90% of the samples are the same value — does the invariant break?No. The size condition counts elements, not distinct values, and the ordering condition allows `top(lower) == top(upper)`, so equal values may sit in both halves. Routing ties down with `<=` keeps the halves filling evenly; routing them up with a strict comparison is still correct but triggers a repair move on roughly every second duplicate. The median is the same number either way, because equal elements are indistinguishable.
- Why is at most one element ever moved during a rebalance?Each insert changes exactly one size by one, so if the difference was in range before, it is out of range by at most one after. Moving a single element flips one count down and the other up, changing the difference by two — exactly enough to bring it back. A loop is not needed, and if you ever find one moving twice, the invariant was already broken before that insert.
- Why must the transfer move a top rather than any element of the heavier heap?The ordering condition has to survive the move. The largest small value is the only element of the lower heap that can legally cross upward, and the smallest large value is the only one that can cross downward. Both are exactly the tops, which is also why the move costs O(log n) rather than a search.
saying these in an interview costs you the question
- States only the size rule and forgets the ordering rule
- Says the heaps must always be exactly equal in size
- Implements only one of the two repair directions
- Claims duplicates break the invariant
- Loops the rebalance instead of moving one element