Maintain the median of a stream under insertions in O(log n) per update. Now allow arbitrary deletions of previously inserted values. Give a structure that still runs in O(log n) amortised and say why lazy deletion alone is not enough.

Maintain the median of a stream under insertions in O(log n) per update. Now allow arbitrary deletions of previously inserted values. Give a structure that still runs in O(log n) amortised and say why lazy deletion alone is not enough.

Approach: Two heaps split the multiset at the median. For deletion, decide what has to remain true about the heap sizes after removing a value buried inside a heap.

Two heaps with lazy deletion plus explicit logical size counters, giving O(log n) amortised. Keep a max heap of the lower half and a min heap of the upper half with sizes differing by at most one, so the median reads off the tops in O(1) while insertion pushes to the correct heap and then rebalances by moving one element, which is O(log n). For deletion, record the value in a to-delete multiset, decrement the logical size of whichever heap holds it, then repeatedly pop any heap top that is marked deleted. Lazy deletion alone fails on two counts. Deleted entries buried in the interior still count toward the physical heap size, so the balance test has to use the logical sizes or the median drifts to the wrong element. Repeated delete then insert of interior values also lets the heaps grow without bound, so the structure must purge or rebuild once the deleted fraction passes a constant, which is where the amortised qualifier comes from. An order-statistic tree gives the same operations in worst case O(log n).

Follow-up: How do you extend the structure to report an arbitrary quantile of a sliding window of the last k values?

Key concepts: two heaps, lazy deletion, rebalancing, logical size.