Problem Statement

The median of a finite list of numbers can be found by arranging all the integers from lowest to highest value and picking the middle one. For example, the median of {3,3,5,9,11} is 5. If there is an even number of integers, then there is no single middle value, and the median is then usually defined to be the mean of the two middle values. For examples, the median of {3,5,7,9} is (5+7)2=6.

Given that integers are read from a data stream, find the median of elements read so far in an efficient way.

Input Format

The first line of input will contain integer N, i.e. the number of integers in the data stream.
Each of the next N lines will contain an integer ai.

Constraints
1≤N≤105
0≤ai≤105

Output Format

Print N integers, i.e. the median after each of the input. Report it with precision up to 10−1.

Sample Input

10
1
2
3
4
5
6
7
8
9
10

Sample Output

1.0
1.5
2.0
2.5
3.0
3.5
4.0
4.5
5.0
5.5

Explanation

See the sorted list after each input

This is a very good example of utilising heap.

The explanation can be understood as follows

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 elements;
     median = (root of maxHeap + root of minHeap)/2
   Else
     median = root of the heap with more elements

 The code is as follows

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
struct compare  
 {  
   bool operator()(const int& l, const int& r)  
   {  
       return l > r;  
   }  
 };  
int arr[100010];
 int main()  
 {  
     int t;
     int n;
     cin>>n;
     for(int i=0;i<n;i++)
     {
      
       cin>>arr[i];
     }
     if(n==1)
     {
      double med=(double)arr[0];
      printf("%.1lf\n",med);
     }
     if(n==2)
     {
         double med1=arr[0];
         double med2=((double)arr[0]+(double)arr[1])/2.0;
         printf("%.1lf \n%.1lf\n",med1,med2);
         cout<<endl;
   }
   else
   {
                      priority_queue<ll,vector<ll>, compare > minheap;  
     priority_queue<ll> maxheap;
       if(arr[0]<arr[1])
       {
             maxheap.push(arr[0]);
      minheap.push(arr[1]);
       
        }
        else{
          minheap.push(arr[0]);
          maxheap.push(arr[1]);
        }
        //cout<<" printed heap "<<endl;
        double med1=arr[0];
         double med2=((double)arr[0]+(double)arr[1])/2.0;
         printf("%.1lf \n%.1lf\n",med1,med2);
  int cntmin=1;
  int cntmax=1;
  for(int i=2;i<n;i++)
  {
   
   //cout<<"whiler entering  "<<maxheap.top()<<" "<<minheap.top()<<endl;
   if(arr[i]<=maxheap.top())
   {
      maxheap.push(arr[i]);
      cntmax++;
     // cout<<"psuing in  amz"<<endl;
   }
   else
   {
      minheap.push(arr[i]);
                cntmin++;
             //   cout<<" pusing in  min "<<endl;
   }
   
        if(abs(cntmin-cntmax)>1)
        {
           if(cntmin>cntmax)
           {
                  
          int val=minheap.top();
          minheap.pop();
          maxheap.push(val);
          cntmin--;
          cntmax++;  
         // cout<<"transferring from min to max "<<endl;
     }
     else
     {
      int val=maxheap.top();
      maxheap.pop();
      minheap.push(val);
      cntmax--;
      cntmin++;
     // cout<<"t frm max to min"<<endl;
     }
           
    }
    double med=0.00;
    if(cntmin>cntmax)
    {
      med=(double)minheap.top();
    }
    else if(cntmax>cntmin)
       med=(double)maxheap.top();
       else
       {
         med=(double)maxheap.top()+minheap.top();
         med=med/2.00;
       }
       printf("%.2lf\n",med);
 //   cout<<"whiler exiting  "<<maxheap.top()<<" "<<minheap.top()<<endl;
           //cout<<cntmin<<" "<<cntmax<<endl;
  }
 }
      return 0;
}