Design a class DataStreamMedian with the following methods:
- DataStreamMedian(): Initializes an empty data structure.
- insert_value(int value): Inserts the integer value into the data structure.
- get_median(): Returns the median of all inserted values as a float. If the number of values is even, return the mean of the two middle values. Answers within 1e-5 of the actual answer are accepted.
You will be given a sequence of method calls and arguments. Return the results of get_median calls as floats, and null for insert_value and initialization calls.
Example 1
Input: ["DataStreamMedian", "insert_value", "insert_value", "get_median", "insert_value", "get_median"] [[], [10], [20], [], [30], []]
Output: [null, null, null, 15.0, null, 20.0]
Explanation: After inserting 10 and 20, median is (10+20)/2=15.0. After inserting 30, values are [10,20,30], median is 20.0.
Example 2
Input: ["DataStreamMedian", "insert_value", "get_median", "insert_value", "insert_value", "get_median"] [[], [5], [], [7], [9], []]
Output: [null, null, 5.0, null, null, 7.0]
Explanation: After inserting 5, median is 5.0. After inserting 7 and 9, values are [5,7,9], median is 7.0.
Constraints
Case 1
Input: ["DataStreamMedian", "insert_value", "insert_value", "get_median", "insert_value", "insert_value", "get_median"] [[], [3], [8], [], [12], [15], []]
Expected: [null, null, null, 5.5, null, null, 10.0]
Case 2
Input: ["DataStreamMedian", "insert_value", "get_median", "insert_value", "get_median"] [[], [-100000], [], [100000], []]
Expected: [null, null, -100000.0, null, 0.0]
Case 3
Input: ["DataStreamMedian", "insert_value", "insert_value", "insert_value", "get_median"] [[], [0], [100], [50], []]
Expected: [null, null, null, null, 50.0]