优先队列
- 思路：
- 中位数是排序中间的数值：S1.M.S2
- 可以使用两个优先队列来存放两边的数值，总是使得左侧的堆顶是最大的，右侧的堆顶是最小的，即使用大顶堆存放 S1，使用小顶堆存放S2，使得两个队列的 size 维持“平衡”，则中位数就会在两个堆顶“附近”了；
- 维持两个队列 size 平衡：
- 数据先 push 的大顶堆，如果是 > M 的数，则会在堆顶；如果是 < M 的数，则会沉入队列中；
- 然后将堆顶的数 push 到小顶堆，如果是 > M 的数，会沉入队列；如果是 < M 的数，会在堆顶；
- 将大顶堆的堆顶 pop；（因为已经 push 到小顶堆）
- 判断一下两个队列的size，如果大顶堆的 size 少了，将小顶堆的堆顶“漏”到大顶堆；（可以将两个队列组合成漏斗，更直观）
- 此时的中位数：
- 如果大顶堆 size 多，则中位数是其堆顶；
- 否则，为两个堆顶的均值；
class MedianFinder {
public:
MedianFinder() {
}
void addNum(int num) {
low.push(num);
high.push(low.top());
low.pop();
if (low.size() < high.size()) {
low.push(high.top());
high.pop();
}
}
double findMedian() {
if (low.size() > high.size()) {
return low.top();
}
return (low.top() + high.top()) / 2.0;
}
private:
std::priority_queue<int, std::vector<int>, std::less<int>> low;
std::priority_queue<int, std::vector<int>, std::greater<int>> high;
};
/**
* Your MedianFinder object will be instantiated and called as such:
* MedianFinder* obj = new MedianFinder();
* obj->addNum(num);
* double param_2 = obj->findMedian();
*/
