vizlearn

Find the median of a data stream

Interview QuestionsBy Updated

Split the values in half: a max-heap of the lower half and a min-heap of the upper half. Their roots are the two middle values, so the median is one or two reads. Each insert pushes, moves one across and rebalances — O(log n) in, O(1) out.

Heaps & top-kCoding problemHard

Step through it

What to watch

  • 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.

Say this 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."

Overview

A running median reports the middle value after each new number. Keep the lower half in a max-heap and the upper half in a min-heap, balance their sizes, then read one or both roots.

Run it

The three-line insert, checked against statistics.median at every step.

1Python
Output
Against re-sorting the stream on every query.
2Python
Output
The heap approach is also substantially faster at scale.
3Python
Output
And what the negation is hiding.
4Python
Output

                

                

                    
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.

                

                

                    
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__.

                

                

                    
Sources and next steps

                    
                

            


        

    



How the code works
The three-line insert, checked against statistics.median at every step, then the cost against re-sorting the stream each time it is queried.
How the code works
  1. heapq.heappush(self.low, -x)Every value goes to the low side first, whatever it is. That is what removes the case analysis.
  2. heapq.heappush(self.high, -heapq.heappop(self.low))Immediately move the low half's largest across. Because the max-heap has floated the biggest value to the root, this guarantees the new value ends up on the correct side.
  3. if len(self.high) > len(self.low)The rebalance. Without it the high half grows by one each insert and the roots stop being the middle.
  4. (-self.low[0] + self.high[0]) / 2Two reads for an even count, one for an odd count. No scan, which is the O(1) being claimed.
Change one thing
  • 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.
  • Feed it a sorted stream instead of a random one. The heaps still balance, because the rebalance depends on sizes rather than on values.
Where this runs
Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.


    



Check yourself
0 of 4
Answer without scrolling back up.
  1. What do the two heap roots represent?
  2. Why push to the low heap and immediately move its largest across?
  3. Why is the low half stored negated?
  4. What are the costs?




        
    



 Cheat sheet
Find the median of a data stream
Keep two heaps as numbers arrive: a max-heap for the lower half and a min-heap for the upper. Report the median after every insertion in O(log n).
INTERVIEW · vizlearn.in/interview/running-median-of-a-stream.html
More in Interview
InterviewWrite binary search without an off-by-oneInterviewFirst and last position of a targetInterviewBinary search on the answer, not the arrayInterviewClimbing stairs: the DP that is Fibonacci
About the author
Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.
About VizLearnGitHubLinkedInContact