This does not seem to work for a list [3,1,-3] assuming you always start inserting in the max heap. Is there any reason why did you started inserting on the max heap for your example?
He did not mention it but when the difference in the size of the heaps becomes 2, you need to rebalance both the heaps. How you do this? If max_heap.size - min_heap.size == 2, then transfer the root element from max_heap to min_heap. Conversely, if min_heap.size - max_heap.size == 2, then transfer the root element from min_heap to max_heap. In your example, initially max_heap ] = [] and min_heap = [] insert(3): max_heap = [3], min_heap = [], median = 3 insert(1): max_heap = [3,1], min_heap = [], difference in size == 2 rebalance: max_heap = [1], min_heap = [3], median = 2 insert(-3): max_heap = [1,-3], min_heap = [3], median = 1 And as you can see it works. There is no reason for starting the insertion on the max_heap, it doesn't matter. You can start on any of the heaps and it would still be correct. If it is still not clear, you can see my submission on LeetCode here: leetcode.com/submissions/detail/299617073/
What if the array started with a one? With your explanation as to why you don't add 9 to the max heap you would have too many values in the min heap.
Great explanation, this is the video which cleared my all doubts....
What to do when the heaps differ by more than 1 element in size: extract the root of the larger heap and push it to the other heap.
Thanks a lot for the video.
I am a self learner. Those algorithm are so hard to catch up :)
What if the difference between the two lists is greater than 1?
This does not seem to work for a list [3,1,-3] assuming you always start inserting in the max heap. Is there any reason why did you started inserting on the max heap for your example?
He did not mention it but when the difference in the size of the heaps becomes 2, you need to rebalance both the heaps. How you do this? If max_heap.size - min_heap.size == 2, then transfer the root element from max_heap to min_heap. Conversely, if min_heap.size - max_heap.size == 2, then transfer the root element from min_heap to max_heap.
In your example, initially max_heap ] = [] and min_heap = []
insert(3): max_heap = [3], min_heap = [], median = 3
insert(1): max_heap = [3,1], min_heap = [], difference in size == 2
rebalance: max_heap = [1], min_heap = [3], median = 2
insert(-3): max_heap = [1,-3], min_heap = [3], median = 1
And as you can see it works. There is no reason for starting the insertion on the max_heap, it doesn't matter. You can start on any of the heaps and it would still be correct.
If it is still not clear, you can see my submission on LeetCode here: leetcode.com/submissions/detail/299617073/
@@mohammedshoaib1635 thank you
very nice explanation
Incomplete Explanation