# My simple c++ solution using heap

• ``````class MedianFinder {
priority_queue<double, vector<double>, greater<double> >left;
priority_queue<double, vector<double>, less<double> >right;
double median=0;
int diff=0;
public:

// Adds a number into the data structure.
diff=left.size()-right.size();
num=double(num);
if(diff==0){
if(median < num){
left.push(num);
median=left.top();
}
else{
right.push(num);
median=right.top();
}
}
else if(diff==1){
if(median < num){
right.push(left.top());
left.pop();
left.push(num);
}
else right.push(num);
median= (left.top() + right.top() )/2;
}
else if(diff== -1){
if(median < num)left.push(num);
else{
left.push(right.top());
right.pop();
right.push(num);
}
median=(left.top() + right.top() )/2;
}
}

// Returns the median of current data stream
double findMedian() {
return median;
}
};``````

• share my easy code using two heaps and very easy to understand.
MAXheap used to hold the half of less number,and minheap used to keep the other number.
so ,according to the size of the two heaps .median element must be either the the top element of maxheap or minheap.code as follow.

``````class MedianFinder {
public:

priority_queue<int,vector<int>,less<int>> maxh;
priority_queue<int, vector<int>, greater<int>> minh;
// Adds a number into the data structure.
maxh.push(num);
if (maxh.size() - minh.size() == 2)
{
minh.push(maxh.top());
maxh.pop();
}
else if (minh.size()>0)
{
maxh.push(minh.top());
minh.pop();
minh.push(maxh.top());
maxh.pop();
}
}

// Returns the median of current data stream
double findMedian() {
if (maxh.size() == minh.size())
{
return (maxh.top()*1.0 + minh.top()*1.0) / 2;
}
else
{
return maxh.top();
}
}
``````

};

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.