Running median of integers

#1

why at the beginning we pushed the element in the left heap? not the right heap?

#2

this is complete algorithm

Algorithm:

  1. Create two heaps. One max heap to maintain elements of lower half and one min heap to maintain elements of higher half at any point of time…
  2. Take initial value of median as 0.
  3. For every newly read element, insert it into either max heap or min-heap and calculate the median based on the following conditions:
  • If the size of max heap is greater than the size of min-heap and the element is less than the previous median then pop the top element from max heap and insert into min-heap and insert the new element to max heap else insert the new element to min-heap. Calculate the new median as the average of top of elements of both max and min heap.
  • If the size of max heap is less than the size of min-heap and the element is greater than the previous median then pop the top element from min-heap and insert into the max heap and insert the new element to min heap else insert the new element to the max heap. Calculate the new median as the average of top of elements of both max and min heap.
  • If the size of both heaps is the same. Then check if the current is less than the previous median or not. If the current element is less than the previous median then insert it to the max heap and a new median will be equal to the top element of max heap. If the current element is greater than the previous median then insert it to min-heap and new median will be equal to the top element of min heap

I hope you understand now that it is obvious to put first element in left heap
if not feel free to ask

#3

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.