Find Running Median

runningmedian.cpp

#include <cmath>
#include <queue>
#include <iomanip>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>


using namespace std;

class runningMedian{
private:
    priority_queue<int> lower;                              //use priority queue container for maxheap
    priority_queue<int, vector<int>, greater<int>> higher;  //use priority queue stl container for minheap

    double median;                                          //initialize variable to hold median, double for average
    void rebalance();                                       //so that no more than difference of 1 number between queues
public:
    void insertNumber(int &);                               //add number
    double getmedian();                                     //function to determine median
};

void runningMedian::insertNumber(int &num){                 
    if(lower.empty() || num < lower.top()){                 //if lower queue empty or number smaller than maxheap, insert here
        lower.push(num);
    }
    else{                                                   //otherwise push it here
        higher.push(num);
    }
    rebalance();                                            //check balance after each insert 
}

void runningMedian::rebalance(){
    if((lower.size() - higher.size()) > 1 || (higher.size() - lower.size()) > 1){ //rebalance function
                                                                                  //check if diff greater than 1
        if(lower.size() > higher.size()){                                         //if greater than 1; push from container 
            higher.push(lower.top());                                             //container that has more than one
            lower.pop();                                                          //pop to remove that number
        }
        else if (lower.size() < higher.size()){
            lower.push(higher.top());
            higher.pop();
        }
    }
}

double runningMedian::getmedian(){                          //if container size is equal, get average of max and min 
    double median;
    if(lower.size() == higher.size()){
        median = (double(lower.top() + higher.top())) / 2;  //use top() 
    }
    else if(lower.size() > higher.size()){                  //if size diff is one, median is top() of container with extra num
        median = lower.top();
    }
    else{
        median = higher.top();
    }
    return median;
}

int main(){
    
    runningMedian med;                                  //declare instance of class
    int n;                                              //number of integers to add
    cin >> n;
    for(int i = 0; i < n; i++){                         //loop to add integers one at a time
        int num;
        cin >> num;
        med.insertNumber(num);                          //number inserted
        cout << setprecision(1) << fixed << med.getmedian() << endl; //median determined after each insert for running median
    }
    return 0;
}