Median of an Integer Stream

Design a data structure that supports the following two operations on a stream of integers:

• add_num(num): add an integer from the data stream to the structure.
• find_median(): return the median of all integers added so far.

If the number of integers seen so far is even, the median is the average of the two middle values. Both operations should run in O(log n) time (or better) with respect to the number of elements added so far — you may not simply sort everything on every call to find_median.

Example

add_num(5)
find_median() -> 5
add_num(2)
find_median() -> 3.5      # average of 2 and 5
add_num(9)
find_median() -> 5        # middle of [2, 5, 9]
add_num(1)
find_median() -> 3.5      # average of 2 and 5, from [1, 2, 5, 9]

Constraints

• Up to 10^5 calls to add_num and find_median combined.
• -10^5 <= num <= 10^5.