Find Median from Data Stream in Python

The median of a list of numbers is the middle value once the list is sorted. When the list has an even number of values, there is no single middle value, and the median is the mean of the two middle values:

• the median of [2, 3, 4] is 3;
• the median of [2, 3] is (2 + 3) / 2 = 2.5.

Numbers arrive one at a time, and at any moment you may be asked for the median of all the numbers that have arrived so far. Implement the class MedianFinder:

• MedianFinder() creates an object that holds no numbers yet.
• addNum(num) adds the integer num to the numbers seen so far.
• findMedian() returns the median of all the numbers added so far.

The input is a list of operations, applied in order to one new MedianFinder. The output lists what the findMedian calls return, in order, each printed with one digit after the decimal point (2.0, 2.5). The starter code spells these names the way your language does.

Example 1:

Input:
    addNum(1)
    addNum(2)
    findMedian()
    addNum(3)
    findMedian()
Output: 1.5 2.0
Explanation:
After 1 and 2, there are two middle values, so the median is (1 + 2) / 2 = 1.5.
After 3 arrives, the sorted numbers are [1, 2, 3], and the middle one is 2.

Example 2:

Input:
    addNum(5)
    findMedian()
    addNum(-3)
    findMedian()
    addNum(-3)
    findMedian()
    addNum(10)
    findMedian()
Output: 5.0 1.0 -3.0 1.0
Explanation:
[5] has the median 5. [-3, 5] has the median (-3 + 5) / 2 = 1.
[-3, -3, 5] has the median -3: a number that arrives twice counts twice.
[-3, -3, 5, 10] has the median (-3 + 5) / 2 = 1.

Example 3:

Input:
    addNum(4)
    addNum(3)
    findMedian()
    findMedian()
    addNum(2)
    addNum(1)
    findMedian()
Output: 3.5 3.5 2.5
Explanation: The numbers don't arrive in sorted order, and asking twice in a row gives the same answer, because findMedian changes nothing. At the end the sorted numbers are [1, 2, 3, 4], so the median is (2 + 3) / 2 = 2.5.

Constraints:

• -105 <= num <= 105
• findMedian is called only after at least one call to addNum.
• At most 5 * 105 calls in total are made to addNum and findMedian.