中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。
- 例如
arr = [2,3,4]的中位数是3。 - 例如
arr = [2,3]的中位数是(2 + 3) / 2 = 2.5。
实现 MedianFinder 类:
MedianFinder()初始化MedianFinder对象。void addNum(int num)将数据流中的整数num添加到数据结构中。double findMedian()返回到目前为止所有元素的中位数。与实际答案相差10-5以内的答案将被接受。
示例 1：
输入
["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
[[], [1], [2], [], [3], []]
输出
[null, null, null, 1.5, null, 2.0]
解释
MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1); // arr = [1]
medianFinder.addNum(2); // arr = [1, 2]
medianFinder.findMedian(); // 返回 1.5 ((1 + 2) / 2)
medianFinder.addNum(3); // arr[1, 2, 3]
medianFinder.findMedian(); // return 2.0提示:
-105 <= num <= 105- 在调用
findMedian之前，数据结构中至少有一个元素 - 最多
5 * 104次调用addNum和findMedian
解题思路一：直接排序（超时）
这种思路比较简单，就是直接在 addNum() 函数中，将 num 插入到数组后直接调用 sort() 函数对数组进行排序，然后在 findMedian() 中就能直接通过索引来得到平均值或者中值！
在处理的时候时间复杂度为 O(nlogn)，在查找中位数的时候时间复杂度为 O(1)，但是在这道题中处理的时候是会超时的，所以不考虑这种方式！
解题思路二：插入排序（超时）
因为每次我们在 addNum() 的时候，其实就只插入了一个元素，那我们可以考虑使用插入排序，因为我们可以让原数组保持有序的情况，只需要处理一个新元素的排序即可，而不需要像解法一中每次调用 addNum() 的时候都需要重新去排序！
那么使用插入排序的时间复杂度对于一个元素来说，是 O(n)，相比解法一有了提升，然后在查找中位数的时候时间复杂度依然是 O(1)，但这道题在处理插入的时候，也耐不住大量极端的数据，所以也是会超时的！
解题思路三：维护大小堆💥
可以看到上面两种解法，其实关键点都在 addNum() 这个函数上，所以我们要想办法优化一下插入的处理！
其实这道题要想到维护大小堆并不简单，但是学会了这种思路，对于相同的问题来说是可以提供一种巧妙的方法的，就是使用一个大堆和小堆来分别维护中位数左右的区间！
说的有些抽象，其实可以参考这幅图：
上图摆的很像一个沙漏的形状，其实最重要的就是两个堆的堆顶元素，对于大堆来说，它要存放的是比中位数小的那一半的值，然后堆顶作为边界，存放的就是这些数中的最大值；对于小堆来说，它要存放的是比中位数大的那一半的值，然后堆顶也是作为边界，存放的这些数中的最小值！
- 如果两个堆的元素和是偶数的话，那么两个堆顶元素的平均值就是中位数！
- 如果两个堆的元素和是奇数的话，那么两个堆中元素个数多的那个堆的堆顶元素，就是中位数！
在插入元素 num 的时候，我们要判断一下 num 和两个堆顶元素的大小关系，我们这里优先判断的是大堆（优先小堆也是可以的，请自行尝试），因为大堆中存放的是较小的那些元素，所以如果 num 小于等于大堆堆顶元素的话，我们就让 num 放入大堆中，反之则放入小堆中！
插入完元素后还没有结束，因为我们在维护这两个堆的时候，要让两个堆的元素个数之差不超过一个元素，超过的话我们需要将元素个数多的那个堆的堆顶 pop 掉，然后放到另一个堆中，这样子就能一直保证两个堆的元素个数之差不超过一个元素！
这样子插入函数 addNum() 就完成了，时间复杂度为 O(logn)，就是堆的插入时间消耗，这可比 O(n) 要快得多！
接着就是 findMedian() 函数，如果两个堆的元素个数总和为奇数的话直接取元素个数多的堆的堆顶返回；如果两个堆的元素总和为偶数，那么取两个堆的堆顶元素的平均值即可！
可以看出查找中位数的时间复杂度依然是 O(1)，是非常优秀的一种结构，既兼顾到了插入，又能快速根据堆顶来索引中位数！
class MedianFinder {
private:
priority_queue<int> bigheap; // 大堆
priority_queue<int, vector<int>, greater<int>> smallheap; // 小堆
public:
MedianFinder() {}
void addNum(int num) {
// 如果大堆没有元素或者num小于等于大堆堆顶的话直接入大堆即可，否则就往小堆中插入
if(bigheap.empty() || num <= bigheap.top())
bigheap.push(num);
else
smallheap.push(num);
// 插入完后判断两个堆的元素个数差距是否大于1
if(bigheap.size() > smallheap.size() + 1)
{
// 如果大堆元素超出要求，则将大堆中堆顶元素放到小堆中去
int top = bigheap.top();
bigheap.pop();
smallheap.push(top);
}
else if(bigheap.size() + 1 < smallheap.size())
{
// 如果小堆元素超出要求，则将小堆中堆顶元素放到大堆中去
int top = smallheap.top();
smallheap.pop();
bigheap.push(top);
}
}
double findMedian() {
// 如果是奇数的话直接取元素个数多的堆的堆顶返回即可！
if(bigheap.size() > smallheap.size())
return bigheap.top();
else if(bigheap.size() < smallheap.size())
return smallheap.top();
return (bigheap.top() + smallheap.top()) / 2.0; // 如果两个堆的元素总和为偶数，那么取两个堆的堆顶元素的平均值
}
};
/**
* Your MedianFinder object will be instantiated and called as such:
* MedianFinder* obj = new MedianFinder();
* obj->addNum(num);
* double param_2 = obj->findMedian();
*/