Find Median from Data Stream
Design a structure that receives integers one at a time and can report the median of all values received so far at any moment. For an even count the median is the mean of the two middle values.
- -10^5 ≤ num ≤ 10^5
- At most 5 · 10^4 calls
- findMedian is called only after at least one add
- Median of a growing stream
- Split values into a lower half and an upper half
- Max-heap for the lower half, min-heap for the upper half
When you repeatedly need the minimum or maximum of a changing collection, a heap gives O(log n) insert and extract instead of re-sorting. "Top k" problems keep a heap of size k for O(n log k); a "median of stream" balances a max-heap of the lower half against a min-heap of the upper half.
Keep a max-heap low for the smaller half and a min-heap high for the larger half, with low allowed to hold one extra element. To add, push onto low, then move its top to high; if high becomes larger than low, move high's top back. This keeps both halves balanced and ordered so the median is low.top or the average of the two tops.
- If values are bounded (e.g. 0..100), a counting array gives O(range) per median. A balanced BST with subtree sizes also works in O(log n).