skip to content

Why does a two-heap running median report a far-too-low value if rebalancing only shrinks the max-heap?

level: seniorimportance: should knowfreq 40%

answer

  1. Which of the two conditions actually breaks?
  2. Try a stream that only ever rises
  3. Nothing ever moves back down
  4. One heap freezes at its first element
  5. The read formula assumes halves are halves

basics

~20 s

Repairing only the max-heap-too-large case lets the min-heap grow without limit whenever samples arrive above the current median, so the max-heap keeps an old small value on top and the reported median sinks toward it. Both repair directions are required.

solid answer

~50 s

Routing sends any sample above the max-heap's top into the min-heap. If the only repair rule is "when the max-heap is two ahead, move its top up", nothing ever moves back down, so a stream of rising latencies piles everything into the min-heap while the max-heap keeps whatever it captured early on. The ordering condition still holds — small values below, large above — so no assertion on values fires and nothing crashes; only the **size** condition is violated, and the median formula is exactly what depends on it. The read then averages a stale small top with the smallest of a huge upper half and drifts far below the truth. The tell is that the error grows with the stream and is worst on monotone input, so the fix is the missing symmetric rule plus an assertion after every insert that the size difference stays within one.

code

pseudocode · 14 lines
pseudocode
// 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))
    // no rule for the case where upper has grown larger

median():
    if size(lower) > size(upper):
        return top(lower)
    return (top(lower) + top(upper)) / 2

go deeper

for a junior

Recall that the repair step has two directions, not one, and that the median formula only works when the two halves stay within one element of each other.

for a middle

Trace a monotone rising stream through the fragment and say exactly which condition survives and which breaks, and why the reported value drifts toward the minimum.

for a senior

Demonstrate the diagnosis: assert on the invariant rather than the output, property-test against a brute-force reference, and choose adversarial input shapes that exercise both repair directions.

for a principal

Own the class of defect — a silently plausible metric — and decide what the team does about it: invariant checks in the hot path, a shadow computation on a sample of traffic, or alerting when a percentile diverges from a cheaper sanity statistic.

## What the fragment does The routing step is correct: a new latency sample goes below when it is at most the max-heap's top, and above otherwise. The repair step is half-written — it handles the case where the lower heap has run two ahead, and has no rule for the upper heap running ahead. ## Why a rising stream exposes it Suppose the collector starts during a warm-up and the very first sample is 4.0 ms, then the service degrades and every subsequent sample is larger than the last: 6.1, 9.4, 15.0, 22.8, 31.5, … - 4.0 goes into the empty lower heap. - 6.1 is greater than 4.0, so it goes up. Sizes are 1 and 1; the one repair rule does not apply. - 9.4 is greater than 4.0, so it goes up. Sizes are 1 and 2. The rule checks whether the *lower* heap is two ahead — it is not — so nothing happens. - Every later sample repeats this. The lower heap is frozen at `{4.0}` and the upper heap swallows the entire stream. After a thousand samples, `size(lower) = 1` and `size(upper) = 999`. The read sees that the lower heap is not larger, so it averages the two tops: 4.0 and the smallest of the upper half. The dashboard reports something close to the *minimum* of the stream and calls it the p50. ## Why nothing fails loudly This is the part worth internalising. Two conditions define the structure, and the bug breaks only one of them. - The **ordering** condition — everything below is at most everything above — is preserved perfectly, because routing was never wrong. Any check of the form `top(lower) <= top(upper)` passes forever. - The **size** condition — the counts differ by at most one — is violated immediately and grows without bound. The median formula is a consequence of the size condition alone: "the tops are the middle values" is only true when the halves are actually halves. So the failure mode is a plausible number, produced with no exception, no memory blow-up beyond what the samples cost anyway, and no log line. On a steady stream that oscillates around a stable median the drift is small and easy to miss; on a monotone or trending stream it is enormous. A second consequence is worth naming: the direction of the error depends on the direction of the drift. A stream of falling latencies pushes everything into the lower heap instead, and there the surviving rule *does* fire, so falling traffic looks fine while rising traffic — exactly the case someone is paging about — reports nonsense. Bugs that only manifest during an incident are the expensive kind. ## Finding it Three checks, in increasing cost: 1. **Assert the invariant, not the output.** After every insert, check that the absolute size difference is at most one and that the tops are ordered. This localises the bug to the insert that broke it instead of to a dashboard someone squints at a week later. 2. **Property-test against a brute-force reference.** Generate random streams, maintain a sorted list alongside, and compare the medians after every sample. A few hundred random samples catch it instantly. 3. **Test the adversarial shapes explicitly.** Strictly increasing, strictly decreasing, all-equal, and alternating-extremes streams each stress a different repair path. A fixture of "typical" jittery latencies passes with the bug in place, which is why hand-picked fixtures are the weakest of the three. ## The fix and its cousins The missing rule is the symmetric one: when the upper heap has more elements than the lower, move its top down. With both rules present, one insert can unbalance the counts by at most one and one move restores them. The same silent-wrong-number family contains two neighbours. **Inverted routing** — pushing large values down and small ones up — breaks the ordering condition instead, and produces a median that is wrong from the second sample onward. **Rebalancing before routing** leaves the just-inserted element in the wrong half with the size counts already repaired, so the structure looks healthy while holding a misplaced element that no later move will ever migrate, since transfers only ever touch the tops. All three share one property: the data structure never notices, so the invariant check has to.

  • Would an assertion that the two tops are correctly ordered have caught this?
    No, and that is the trap. Routing is correct, so every small value really is below every large one and `top(lower) <= top(upper)` holds forever. The condition that breaks is the size one, so the assertion that catches it is `abs(size(lower) - size(upper)) <= 1` after every insert. Checking values instead of counts gives false confidence.
  • Why does a stream of falling latencies hide the bug?
    Falling samples route into the lower heap, which is the case the surviving rule repairs, so the structure stays balanced and the median is right. The defect only shows when the untreated direction is exercised. That asymmetry is why test streams must include monotone increasing, monotone decreasing and all-equal shapes rather than one plausible jittery fixture.
  • What happens if you run the rebalance before routing the new sample?
    The counts get repaired against the old state and then the new sample lands, so the structure ends one element out of balance and, worse, can end with a value in the wrong half. Transfers only ever move tops, so a misplaced interior element never migrates back — it stays wrong for the life of the process. Route first, then repair.

saying these in an interview costs you the question

  • Says the structure would crash or throw
  • Blames duplicate values instead of the missing repair rule
  • Asserts the tops are ordered and calls it verified
  • Thinks the ordering condition is the one violated
  • Tests only with a realistic jittery sample stream

context

resolving links…