Find Median from Data Stream

Problem

Design a class MedianFinder that receives integers one at a time and can report the median of everything received so far.

• MedianFinder() creates an empty structure.
• addNum(num) inserts one integer.
• findMedian() returns the median as a float: the middle value when the count is odd, or the mean of the two middle values when the count is even.

findMedian is only called when at least one number has been added.

• Values fit comfortably in a normal int, positive or negative.
• Up to several tens of thousands of calls to addNum and findMedian combined.

Examples

• addNum(4), addNum(9), findMedian() → 6.5; then addNum(2), findMedian() → 4.0. Two numbers average to 6.5; with three numbers (2, 4, 9 sorted) the middle one is 4.
• addNum(7), findMedian() → 7.0. A single value is its own median.
• addNum(-3), addNum(-3), addNum(6), findMedian() → -3.0. Duplicates count separately; the sorted stream is -3, -3, 6.

Hints

1. The median splits the data into a lower half and an upper half. Which single value from each half do you need to compute it?
2. You need fast access to the largest of the lower half and the smallest of the upper half, plus a cheap way to move one element between halves when they become unbalanced.
3. Two heaps: a max-heap for the lower half and a min-heap for the upper half, kept within one element of each other in size.