295. Find Median from Data Stream

Description:

Solution:

In the Heap,  Add elements, remove elements: O(logn), Find Max/Min elements: O(1)

ex)

1. add(3): Add to small heap[O(logn)]

2. add(2): Add to small heap, small heap: 2, large heap: 0, so we find the maximum value of small heap[O(1)], and add it to large heap(O(logn)]

3. add(7): Add to small heap[O(logn)], 7 is bigger than 3, so find the max[O(1)], move to large heap[O(logn)]

4. add(4): Add to small heap[O(logn), 4 is bigger than 3, so find the max[O(1)],  move to large heap[O(logn)]. But small heap: 1, large heap: 3, so we find the minimum value of large heap[O(1)], and add it to small heap [O(logn)].