The running median of stream of integers problem

#1

please tell me how to implement this code as Im not able to do so

#2

Hey @aslesha.j7
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…
Take initial value of median as 0.
For the first two elements add smaller one to the maxHeap on the left, and bigger one to the minHeap on the right. Then process stream data one by one,

Step 1: Add next item to one of the heaps

if next item is smaller than maxHeap root add it to maxHeap,
else add it to minHeap

Step 2: Balance the heaps (after this step heaps will be either balanced or
one of them will contain 1 more item)

if number of elements in one of the heaps is greater than the other by
more than 1, remove the root element from the one containing more elements and
add to the other one
Then at any given time you can calculate median like this:

If the heaps contain equal amount of elements;
median = (root of maxHeap + root of minHeap)/2
Else
median = root of the heap with more elements

#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.