https://leetcode.com/problems/find-median-from-data-stream/
class MedianFinder {
public:
priority_queue<int> maxQueue;
priority_queue<int, vector<int>, greater<int>> minQueue;
// Adds a number into the data structure.
void addNum(int num) {
if (!minQueue.empty() && num > minQueue.top()) {
minQueue.push(num);
} else {
maxQueue.push(num);
}
if (maxQueue.size() > minQueue.size() + 1) {
minQueue.push(maxQueue.top());
maxQueue.pop();
}
if (maxQueue.size() < minQueue.size()) {
maxQueue.push(minQueue.top());
minQueue.pop();
}
}
// Returns the median of current data stream
double findMedian() {
double val = maxQueue.size() > minQueue.size() ? maxQueue.top() : minQueue.top();
if (maxQueue.size() == minQueue.size()) {
val = static_cast<double>(maxQueue.top() + minQueue.top()) / 2;
}
return val;
}
};
// Your MedianFinder object will be instantiated and called as such:
// MedianFinder mf;
// mf.addNum(1);
// mf.findMedian();
