Run it
The three-line insert, checked against statistics.median at every step.
Against re-sorting the stream on every query.
And what the negation is hiding.
Why two heaps and not one sorted list
A sorted list gives an O(1) median and an O(n) insert, because everything after the insertion point shifts. A single heap gives an O(log n) insert and no useful median at all — a heap knows its extreme, not its middle.
Two heaps back to back give both. The largest of the small half and the smallest of the large half sit next to each other in sorted order, and both are heap roots. So the structure keeps exactly the two values you need at exactly the two positions a heap makes cheap.
The insert, and why it is three operations
The naive version — compare against a root and push to the appropriate side — is correct and has an awkward number of cases. The compact form has none:
heappush(low, -x) # always to the low side
heappush(high, -heappop(low)) # move its largest across
if len(high) > len(low):
heappush(low, -heappop(high)) # rebalance
Pushing then immediately moving the largest guarantees the value lands on the correct side whatever it was, because the max-heap has already floated the biggest low value to the top. The third line keeps the sizes within one. Three heap operations, no branching on value, and it is the version worth memorising.
The negation, and what it costs
heapq implements a min-heap only, so a max-heap is built by negating on the way in and again on the way out. It works for numbers and it is the standard trick.
It does not work for anything that is not negatable — strings, tuples, objects. For those, either wrap each item in a class with a reversed __lt__, or push (-priority, item) when only the key needs reversing. Mentioning the limitation is worth doing, because the negation trick is the first thing that breaks when the question changes from integers to records.
The follow-ups
"What about a sliding window median?" Harder, because values now leave as well as arrive and a heap cannot remove an arbitrary element. The standard answer is lazy deletion: keep a count of values due to be removed and discard them when they reach a root. The other answer is a structure built for it, like a sorted container with O(log n) insert and delete.
"What if you only need an approximate median?" Then this is overkill, and the real-world answer is a sketch — t-digest or a reservoir sample — which trades exactness for constant memory. Worth naming, because production percentile monitoring is built on those rather than on two heaps.
What to say out loud
Two heaps. A max-heap for the lower half, a min-heap for the upper half, kept within one element of each other in size. The median is the root of the larger heap, or the average of the two roots when they are equal. Insert is O(log n) and the median is O(1). Python only has a min-heap, so the low half stores negated values.
Edge cases to raise
Volunteering these is most of what separates a correct answer from a good one.
The first element. One heap is empty, so any median that reads both roots will raise. The size check has to come first.
Even counts. The median is the average of two roots, so the return type becomes a float. Returning an int for odd counts and a float for even ones is a real inconsistency to decide on deliberately.
The negation only works for numbers. Strings, tuples and objects cannot be negated, so a max-heap of those needs a wrapper class with a reversed __lt__.
The follow-ups interviewers ask
"Now do a sliding-window median." Harder, because values leave as well as arrive and a heap cannot delete an arbitrary element. The standard answer is lazy deletion - count what is due to be removed and discard it when it surfaces at a root - or a structure built for it, such as a sorted container with O(log n) insert and delete.
"What if you only need an approximate median?" Then two heaps are overkill. t-digest or a reservoir sample gives percentiles in constant memory, which is what production monitoring actually uses.
"Report an arbitrary percentile, not the median." The same split with the sizes kept at a different ratio - the roots then straddle the 90th percentile instead of the middle. Getting the rebalance condition right is the whole change.
Common wrong answers
"Keep a sorted list and index the middle." O(1) median and O(n) insert, because everything after the insertion point shifts. It is the baseline to mention and not the answer.
"Use one heap." A heap knows its extreme, not its middle. There is no way to read a median off a single heap.
"Compare against a root and push to the right side." Correct, and it has more cases than the three-line version - and the cases are where the bugs live. Push low, move the max across, rebalance.
Recap in one screen
- The two roots are the middle of the data - that is the whole design.
- Every insert goes through both heaps, which is what keeps them balanced.
- The low half is negated, because heapq is a min-heap only.
- Worth trying: Remove the rebalance line and watch the medians drift. It fails silently rather than raising, which is why the check against statistics.median is in the code.
- Worth trying: Feed it a sorted stream instead of a random one. The heaps still balance, because the rebalance depends on sizes rather than on values.