How do you keep a two-heap median over a fixed trailing window when the expiring sample isn't at a top?

## Why the window changes the problem A dashboard showing the median latency of the last 10,000 requests, rather than of all time, needs one removal for every insertion once the window is full. Insertion is the operation heaps are built for. Removal is not: a heap orders parents against children only, so the departing sample sits at an unknown position and finding it is a linear scan. Doing that per step turns an O(log n) structure into an O(n) one. ## Lazy deletion The trick is to defer the removal until the element reaches a top, where deletion is cheap. Maintain, besides the two heaps: - a table of **pending removals**, counting how many copies of each departing value are logically gone, - two **logical sizes**, one per half, counting only the elements that are still in the window. When sample `x` falls out of the window: compare it against the max-heap's top to decide which half it is in (`x <= top(lower)` means it is below), increment its pending count, and decrement that half's logical size. Nothing is searched or moved. Before any read of a top — for the median, for routing, or during a rebalance — run a purge loop on that heap: while its top has a positive pending count, pop it and decrement the count. Only a top can be purged, which is exactly the operation a heap supports cheaply. Rebalancing then runs on the **logical** sizes. This is the single most common mistake in the pattern: the physical arrays are bloated with dead elements, so comparing their lengths puts the boundary in the wrong place and returns a wrong median even though every individual step looked correct. ## Cost and memory Each sample is pushed once and popped at most once, so the total work over a stream of length N is O(N log n) — amortised O(log n) per window step, even though a single step may purge a run of stale tops. Memory is the price. A heap may physically hold far more than the window's worth of elements if dead ones are buried deep and never surface. In the worst case, dead elements accumulate until they reach a top. Two mitigations are usual: purge opportunistically at both tops on every step, and rebuild both heaps from the live elements when the physical size exceeds, say, twice the logical size. The rebuild is O(n) but pays for itself over the n steps that filled the slack, so the amortised bound is unchanged. ## Identity, not equality Counting pending removals by *value* works when values are exact and repeats are interchangeable, which for rounded millisecond latencies they are. It gets subtle with floating-point values that are computed rather than stored verbatim: purging keys on equality against a value that was rounded or re-derived can miss. The robust form stores a sequence number with each sample and marks removals by that identifier, so a purge is unambiguous and duplicates cannot confuse the counts. It costs one extra field per element and removes an entire class of "the median drifts after a few hours" bugs. ## The alternative: an indexed heap If you want a hard bound instead of an amortised one, make the heap indexed: alongside the array, keep a map from element handle to its current array position, and update that map inside every sift-up and sift-down. Deleting an arbitrary element then means looking up its position, swapping in the last element, and sifting it in whichever direction it needs — O(log n) worst case, with no dead elements and no memory slack. The cost is that every structural move now writes to two places, which is both slower by a constant factor and much easier to get wrong; forgetting to update the map inside one sift branch produces stale positions and corrupt deletions that surface only under specific input shapes. Lazy deletion is a dozen lines and is the usual choice; the indexed heap earns its keep when memory is tight or when deletions vastly outnumber reads. ## When to abandon the pattern If the window also needs arbitrary order statistics — p50 and p90 and p99 from the same window — the two-heap split stops paying, because it maintains exactly one boundary. A balanced search structure augmented with subtree counts answers any rank in O(log n) with a single copy of the data, and supports removal natively. The two-heap version wins when there is one percentile, reads are frequent, and the implementation must stay small enough for the on-call engineer to read.