1. insertNum(3)
2. insertNum(1)
3. findMedian() -> output: 2
4. insertNum(5)
5. findMedian() -> output: 3
6. insertNum(4)
7. findMedian() -> output: 3.5
class MedianFinder {
public:
/** initialize your data structure here. */
MedianFinder() {
}
void addNum(int num) {
if(maxHeap.empty() or num <= maxHeap.top()) {
maxHeap.push(num);
}
else {
minHeap.push(num);
}
if( maxHeap.size() > minHeap.size() + 1) {
minHeap.push(maxHeap.top());
maxHeap.pop();
}
else if( minHeap.size() > maxHeap.size() ) {
maxHeap.push(minHeap.top());
minHeap.pop();
}
}
double findMedian() {
if(maxHeap.size() == minHeap.size()) {
return maxHeap.top() / 2.0 + minHeap.top() / 2.0;
}
return maxHeap.top();
}
private:
priority_queue<int, vector<int>, greater<int>> minHeap;
priority_queue<int> maxHeap;
};
/**
* Your MedianFinder object will be instantiated and called as such:
* MedianFinder* obj = new MedianFinder();
* obj->addNum(num);
* double param_2 = obj->findMedian();
*/