Find Median from Data Stream
Balance a max-heap of the low half against a min-heap of the high half.
Approach
Keep a max-heap for the smaller half and a min-heap for the larger half, rebalancing so their sizes differ by at most one. The median is the top of the larger heap (odd count) or the average of both tops (even). Each insert is O(log n); median is O(1).
Time complexity
O(log n) add, O(1) median
Space complexity
O(n)
Common mistake
Letting the heaps drift out of balance, so the tops no longer straddle the true median.
See it run, step by step
Generate an interactive lesson for Find Median from Data Stream — trace every variable and watch the algorithm execute until it clicks.
Start a lesson on Find Median from Data Stream