Hard
Maintain a running median as numbers are inserted.
Design a data structure that supports adding numbers from a stream and retrieving the median at any time.
Examples
Input: addNum(1), addNum(2), findMedian(), addNum(3), findMedian()
Output: 1.5 then 2.0
Constraints
- Many operations may be interleaved