难度困难387
如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。
例如，
[2,3,4] 的中位数是 3
[2,3] 的中位数是 (2 + 3) / 2 = 2.5
设计一个支持以下两种操作的数据结构：
- void addNum(int num) - 从数据流中添加一个整数到数据结构中。
- double findMedian() - 返回目前所有元素的中位数。
示例 1：
输入：
["MedianFinder","addNum","addNum","findMedian","addNum","findMedian"]
[[],[1],[2],[],[3],[]]
输出：[null,null,null,1.50000,null,2.00000]示例 2：
输入：
["MedianFinder","addNum","findMedian","addNum","findMedian"]
[[],[2],[],[3],[]]
输出：[null,null,2.00000,null,2.50000]限制：
- 最多会对
addNum、findMedian进行50000次调用。
注意：本题与主站 295 题相同：https://leetcode-cn.com/problems/find-median-from-data-stream/
设计思路：优先级队列
原本我是想不出用优先级队列的，所以一开始我是用 vector 也就是数组然后通过插入排序来插入，虽说能达到获取中位数的时候是 O(1) ，但是在插入过程中可能达到 O(n) 的时间复杂度，所以看了一下题解，可以用优先级队列来优化！
优化思路：用两个优先级队列，一个是大顶堆另一个是小顶堆来分别记录 “较小的一半”、“较大的一半”，并且记录过程中保持让两个优先级队列的元素个数相差 1 个。
这样子如果是偶数个元素的话，我们只需要返回两个堆的堆顶，也就是 较小一半中的最大值 和 较大一半的最小值 的一半，也就是它们的中位数了；如果是奇数个元素的话，我们只需要返回元素个数多的那个堆的堆顶即可，因为多出来的这个元素让中位数变成了是一个单独的值而不是两个数的平均值！
除此之外，这个过程中插入元素有一个重要的点，就是插入的元素可能会破坏原来两个堆的递增顺序，下面以大顶堆为例，大顶堆是存放的 “较小的那一半”：
- 如果我们插入的 num 刚好就是 ”较小的那一半“，那么插入到 bigheap 也就是大顶堆中，不会破坏两个堆之间的相对顺序的，因为小顶堆中放的都是 ”较大的那一半“。
- 如果我们插入的 num 刚好就是 ”较大的那一半“，那么插入到 bigheap 也就是大顶堆中，两个堆的相对顺序就被破坏了，因为有可能大顶堆的堆顶比小顶堆的堆顶还大，这样子中位数就错了！
为了避免这种情况，我们使用如下方法来解决：
- 我们可以先将这个要插入的 num 插入到另一个堆中，另一个堆可能就会重新更新堆顶，然后再将另一个堆的堆顶插入到原来要插入的堆中，最后将另一个堆的堆顶 pop 掉，就能避免这种情况了！
最后流程图如下：
class MedianFinder {
public:
/** initialize your data structure here. */
MedianFinder() {}
void addNum(int num) {
// 每次需要插入另一个堆后，再拿取另一个堆的最值才能保持顺序
if(bigheap.size() == smallheap.size())
{
smallheap.push(num);
bigheap.push(smallheap.top());
smallheap.pop();
}
else
{
bigheap.push(num);
smallheap.push(bigheap.top());
bigheap.pop();
}
}
double findMedian() {
// 个数相同说明是偶数个，不同则是奇数个，这里默认设为bigheap的个数多
if(bigheap.size() == smallheap.size())
return (bigheap.top() + smallheap.top()) / 2.0;
else
return bigheap.top();
}
private:
priority_queue<int> bigheap; // 大顶堆，存放较小的那一半
priority_queue<int, vector<int>, greater<int>> smallheap; // 小顶堆，存放较大的那一半
};
/**
* Your MedianFinder object will be instantiated and called as such:
* MedianFinder* obj = new MedianFinder();
* obj->addNum(num);
* double param_2 = obj->findMedian();
*/