Design a data structure that supports inserting numbers from a stream and returning the current median after each insertion. The usual approach is to balance a max heap for the lower half and a min heap for the upper half.
nums = stream values in insertion order
median after each insertion
Example 1:
Input:
nums = [1,2,3,4]
Output:
[1.0,1.5,2.0,2.5]
Explanation:
The median is updated after every insertion.
Example 2:
Input:
nums = [5,15,1,3]
Output:
[5.0,10.0,5.0,4.0]
Explanation:
The heap balance changes as smaller and larger values arrive.