Median Maintenance with Two Heaps
You'll learn how to efficiently track the median of a data stream by using two heaps working in tandem.
The Core Challenge
Imagine you're receiving numbers one at a time and need to instantly report the median after each arrival. The naïve approach—sorting the entire list each time—takes O(n log n) per number. We can do much better with a clever two-heap structure.
The Two-Heap Strategy
Split your numbers into two balanced halves:
- Max-heap holds the smaller half of numbers (largest value at the top)
- Min-heap holds the larger half of numbers (smallest value at the top)
Think of it like two mountains facing each other: the max-heap's peak points upward showing the largest small number, while the min-heap's peak points upward showing the smallest large number. The median lives right between these two peaks!
How It Works
- Insert new numbers: Add to one heap based on comparison with current median
- Rebalance: Keep heaps equal in size (or differ by 1) by moving the top element from one heap to the other
- Find median:
- If heaps are equal size, median is the average of both tops
- Otherwise, median is the top of the larger heap
Each insertion takes O(log n) time, and finding the median is instant O(1).
Example Walk-Through
Stream: [5, 15, 1, 3]
- Add 5: max-heap=
[5], min-heap=[], median=5 - Add 15: max-heap=
[5], min-heap=[15], median=10 - Add 1: max-heap=
[5,1], min-heap=[15], rebalance → max-heap=[1], min-heap=[5,15], median=5 - Add 3: max-heap=
[3,1], min-heap=[5,15], median=4
Key Takeaway: Maintaining a running median efficiently requires splitting data into two balanced heaps—a max-heap for the lower half and a min-heap for the upper half—giving O(log n) insertions and O(1) median queries.