Find Median from Data Stream - Hard Python Heap / Priority Queue Interview Problem

Design a data structure that supports the following two operations:

addNum(num): Add an integer num from the data stream to the data structure.
findMedian(): Return the median of all elements so far.

If the total count of elements is even, the median is the average of the two middle values. If odd, the median is the middle value.

Example

Input: addNum(1), addNum(2), findMedian(), addNum(3), findMedian()
Output: 1.5, 2.0
Explanation: After [1,2] the median is (1+2)/2 = 1.5; after [1,2,3] the median is the middle value 2.

Constraints

-10^5 <= num <= 10^5
At most 5 * 10^4 calls will be made to addNum and findMedian.
There will be at least one element before any call to findMedian.

Hints