Why does a running median over a live stream use two heaps rather than one sorted buffer?

## The problem being solved A monitoring agent receives API request durations in milliseconds, one sample at a time, and the dashboard must show the p50 — the median of everything seen so far — refreshed after every sample. Two costs matter and they pull in opposite directions: the cost of **absorbing** a new sample, and the cost of **answering** "what is the median right now". ## Why the obvious structures lose **Unsorted buffer.** Appending is O(1), but the median is not sitting anywhere in particular, so every read is a selection pass over all n samples — O(n) at best, O(n log n) if you just sort each time. On a dashboard that reads after every sample, that is quadratic work over the stream. **Sorted buffer.** Now the read is O(1): index the middle. But insertion is O(n). This is the misconception worth killing outright: locating the insertion point by binary search is O(log n), yet making room for the new value shifts on average half the elements, and shifting dominates. "The search is logarithmic" says nothing about the insert. **One heap holding everything.** A heap is a partial order, not a total one; it promises the extreme on top and nothing about the middle. Reading the median from a single heap means popping roughly n/2 times and pushing everything back — O(n log n) per read, the worst of the three. ## The two-heap split Split the samples seen so far into two halves at the median boundary: - `lower` — a **max-heap** holding the smaller half. Its top is the **largest** of the small values. - `upper` — a **min-heap** holding the larger half. Its top is the **smallest** of the large values. Two properties are maintained: every value in `lower` is at most every value in `upper`, and the sizes differ by at most one (by convention `lower` carries the extra when the count is odd). Given those, the median is immediate. Odd count: `lower` has one more element, and its top is exactly the middle value. Even count: the two middle values are the two tops, so the median is their mean. No traversal, no popping — an O(1) read that does not mutate anything. Absorbing a sample is a push into whichever half it belongs to, followed by at most one transfer of a top from the heavier heap to the lighter one. Both are O(log n), so the per-sample cost is O(log n). ## The cost picture | approach | insert | median read | memory | |---|---|---|---| | unsorted buffer | O(1) | O(n) | O(n) | | sorted buffer | O(n) | O(1) | O(n) | | single heap of all samples | O(log n) | O(n log n) | O(n) | | two heaps | O(log n) | O(1) | O(n) | All four hold every sample, so none of them wins on memory; the two-heap version wins because it is the only one cheap on **both** axes at once. ## A detail the plumbing forces on you Mainstream runtimes disagree on whether a max-heap exists at all: several (Python's and Go's standard heaps, for instance) expose only a min-oriented heap, so the lower half is kept either by negating the stored keys or by supplying a reversed ordering, while others (Java, C++) hand you an explicit comparator or a max-oriented container directly. The algorithm is identical in every case — only the way you spell "largest on top" changes. ## What the structure does not give you It gives you *one* boundary, the one you chose to maintain. It does not give arbitrary removal (heaps expose only their top), it does not give the k-th smallest for arbitrary k, and it does not merge with another agent's copy — you cannot combine two medians into a global median. Memory also grows with the stream, one slot per sample forever, which is what pushes long-running collectors toward a bounded window or an approximate estimator. The same split generalises: to track the p90 instead of the p50, keep the size ratio at 9:1 rather than 1:1 and read the top of the lower heap. The structure is unchanged; only the target sizes move.