Median using TwoHeaps
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>


class Median {
private:
std::priority_queue<int> small;
std::priority_queue<int, std::vector<int>, std::greater<int>> large;
public:
void insert(int num){
small.push(num);
if(!small.empty() && !large.empty() && (small.top() > large.top())){
large.push(small.top());
small.pop();
}

if(small.size() > large.size() + 1){
large.push(small.top());
small.pop();
} else if (large.size() > small.size() + 1){
small.push(large.top());
large.pop();
}
}

double get_median(){

if(small.size() > large.size())
return small.top();
else if(large.size() > small.size())
return large.top();
else
return ((small.top() + large.top()) / 2.0);
}

};


int main(){
Median* m = new Median();

m->insert(4);
m->insert(7);
m->insert(3);
m->insert(5);
m->insert(1);

std::cout << m->get_median() << '\n';


return 0;
}