Find Median from Data Stream

Find Median from Data Stream: design a MedianFinder with addNum(num), which adds a number from a stream, and findMedian(), which returns the median of all numbers added so far — the middle value, or the average of the two middle values when the count is even.

Example: addNum(1), addNum(2), findMedian() → 1.5; addNum(3), findMedian() → 2.

Store the numbers in a sorted array and insert each new one in place; the median is then the middle element. findMedian is O(1), but every insertion shifts elements: O(n) per addNum. Re-sorting on every query is worse, O(n log n). The median only ever depends on the two middle values, so the rest of the order is wasted work.

Split the numbers into a lower half and an upper half. The median only needs the largest of the lower half and the smallest of the upper half — exactly what a max-heap and a min-heap expose in O(1).

1. low (max-heap) holds the smaller half; high (min-heap) the larger half.
2. addNum: push onto low, then move low's largest to high — so everything in low stays ≤ everything in high.
3. If high now has more elements than low, move high's smallest back. low keeps the extra element when the count is odd.
4. findMedian: low's top if low is bigger, else the average of both tops.

The stream runs along the top. Below it, low and high are drawn back to back with their tops at the seam, so the median always sits in the middle. Each add shows the push, the crossing to high, and any rebalance; then the median is read from the top or tops.