Median from Stream
Add numbers alternately to each heap (always maintaining balance). Max-heap top = largest of the small half. Min-heap top = smallest of the large half. Median is either the larger heap's top or the average of both tops.
How It Works
The two-heap median structure splits the numbers seen so far into halves: a max-heap holds the smaller half and a min-heap holds the larger half. The tops of the two heaps sit adjacent to the median. On each insertion, route the number to the correct heap (compare with the max-heap's top), then rebalance so the size difference never exceeds one — pop from the bigger heap and push onto the other. The median is then the top of the larger heap, or the average of both tops when sizes are equal.
Each insertion costs O(log n) for a constant number of heap operations, and every median query is O(1). A sorted-array approach pays O(n) per insertion for shifting; re-sorting pays O(n log n). The two heaps maintain just enough order — partitioned around the middle — instead of total order, which is why they win.
Step-by-Step Visualization
Code
// Same as MedianFinder implementation
// Max-heap holds smaller half, min-heap holds larger half
// Median = top of max-heap (odd count)
// or average of both tops (even count)Tips & Gotchas
Practice Problems
- 1Find Median from Data Stream
- 2Sliding Window Median
- 3IPO
About the Two Heaps Pattern
Split a stream of numbers into two halves: a max-heap for the smaller half and a min-heap for the larger half. The median is at the tops of the heaps. Rebalance to keep their sizes within 1 of each other.
Need the K largest? Use a min-heap of size K — anything larger than the min gets in. For median, split into two heaps: max-heap for lower half, min-heap for upper half.
Common Heap Interview Problems
- Kth Largest Element
- Top K Frequent Elements
- Find Median from Data Stream
- Merge K Sorted Lists
- Task Scheduler
- K Closest Points to Origin
Frequently Asked Questions
Why keep the middle at heap tops instead of a fully sorted structure?
The median only ever needs the boundary between the lower and upper halves, so maintaining total order is wasted work. Two heaps maintain exactly that boundary in O(log n) per update, whereas inserting into a sorted array costs O(n) for element shifting.
What is the most common implementation bug in this pattern?
Rebalancing errors: pushing to a heap without checking sizes afterward, or letting the size gap reach two. A clean discipline is to always push into one designated heap first, then move the top across, then rebalance — this normalizes every case. Also remember most languages provide only min-heaps, so the max-heap side needs negated values or a reversed comparator.
Does this extend to arbitrary percentiles?
Yes — to track the pth percentile, keep the lower heap holding roughly p percent of elements and the upper heap the rest, rebalancing to that target ratio instead of a 50/50 split. The query stays O(1) at the heap tops.