为了动态维护中位数，我们可以建立两个二叉堆：一个小根堆、一个大根堆。
在依次读入这个整数序列的过程中，设当前序列长度为M，我们始终保持：
- 序列中从小到大排名为1 ~ M/2的整数存储在大根堆中;
- 序列中从小到大排名为M/2+1 ~ M的整数存储在小根堆中，
- 大根堆允许存储的元素最多比小根堆多一个。
任何时候，如果某一个堆中元素个数过多， 打破了这个性质，就取出该堆的堆顶插入另一个堆。
class MedianFinder {
public:
priority_queue<int> maxHeap;
priority_queue<int, vector<int>, greater<int>> minHeap;
/** initialize your data structure here. */
MedianFinder() {
}
void addNum(int num) {
if (maxHeap.empty() || 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() {
return maxHeap.size() == minHeap.size() ? (maxHeap.top() + minHeap.top()) / 2.0 : maxHeap.top();
}
};
/**
* Your MedianFinder object will be instantiated and called as such:
* MedianFinder* obj = new MedianFinder();
* obj->addNum(num);
* double param_2 = obj->findMedian();
*/