Thursday, October 22, 2015

Function to find median from an array of integers

#include <iostream>
#include <sstream>
#include <vector>
#include <queue>
#include <stdlib.h>
#include <iomanip>

using namespace std;

void GetMedian(int arr[], int len)
{
    priority_queue <int, vector <int>, greater <int>> minheap;
   
    priority_queue <int, vector <int>, less <int>> maxheap;
   
    int i, x;
   
    for (i=0; i<len; i++)
    {
        x = arr[i];
        if (!maxheap.empty() && x > maxheap.top()) {
            minheap.emplace(x);
        } else {
            maxheap.emplace(x);
        }
        if (minheap.size() > maxheap.size() + 1) {
            maxheap.emplace(minheap.top());
            minheap.pop();
        } else if (maxheap.size() > minheap.size() + 1) {
            minheap.emplace(maxheap.top());
            maxheap.pop();
        }
       
        cout << fixed;
        cout << setprecision(1);
       
        if (minheap.size() == maxheap.size()) {
            cout << (double) (0.5 * (minheap.top() + maxheap.top())) << endl;
        } else {
            cout << (double) ((minheap.size() > maxheap.size() ? minheap.top() : maxheap.top())) << endl;
        }
    }
}

int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */  
    int N, i;
   
    cin >> N;
   
    int A[N];
   
    for (i = 0; i < N; i++)
    {
        cin >> A[i];
    }
   
    GetMedian(A, N);
   
    return 0;
}