generate median for running stream of integers

15.cpp

/*
Maintain two heaps. maxheap and minheap
The difference between elements in both heaps is atmost 1.
if elements in both heaps are equal, then take the average of two root elements of two heaps.
else return the root element of max heap.
if diff of elements is more than 1, then add those root elements in max heap to minheap and adjust maxheap.
voila, you will get your answer.
for heap:- https://github.com/rohspeed/Algo-world/blob/master/dsa_easy/heap_sort.cpp
pseudo code
*/

void generate_regular_stream(){
  heap *h1 = maxheap();
  heap *h2 = minheap();
  while(1){
    int n;
    cin >> n;
    if(h1.size() - h2.size() > 1){
      node *rt = h1.top();
      heapify(h1);
      h1.pop();
      h2.push(rt);
    }
    if(h1.size() == h2.size()){
      return (h1->root + h2 -> root)/2;
    }
    else 
      return h1->root;
  }
}