「堆」对顶堆 / LeetCode 295（C++）
目录
概述
LeetCode 295：
中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。
- 例如
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]
堆允许我们以logn的时间复杂度查询元素最大/最小值。那如果我们要查询第k大的元素呢？
随机快速选择是一个好方法。那如果我们的数据量总是动态变化呢？
有请主角：对顶堆。
思路
对顶堆，故名思议，两个头碰头的堆。
对顶堆可以在元素动态变化时维护第k小/大的元素。
具体地，对顶堆左侧是大根堆，右侧是小根堆，他们头碰头对顶，而对顶位置就是第k个元素。
二叉树描述 堆化数组描述
|
||
| ||||
|| ||||||
|||| |||||||||
||||||| |||||||||||| i 0 1 2 .......k......................
|大根堆||| K |||小根堆|||| nums[i] [ > > > > >]>|<[< < < < < < < < < < ]
||||||| ||||||||||||
|||| |||||||||
|| ||||||
| ||||
||
|
------------------------→ ----------------------------------→
元素增大 元素增大实现对顶堆通常采用堆化数组实现，不过好在C++已经给我们提供priority_queue优先队列实现了堆化数组的功能。
*注意*：考虑题目并未要求对元素删除，我们可以使用priority_queue，它的结构更简单，但不支持堆顶最值弹出外的其他删除操作。如果我们需要动态变更元素，应该考虑std::set（有序集合），它也支持logn级别的访问操作，同时支持logn级别的任意元素删除（set底层其实是一颗红黑树，叫做对顶红黑树更合适）。
算法过程
求出数据流的中位数，我们可以形成这样一个对顶堆：
偶数个数据时，大根堆（左侧元素）与小根堆（右侧元素）大小相同。
奇数个数据时，大根堆（左侧元素）比小根堆（右侧元素）小1个元素。
由于左侧元素小于右侧元素，我们称大根堆（左侧元素）为small，小根堆（右侧元素）为big。
加入数据num时，我们有以下判断：
①大跟堆small的size等于小根堆big的size时（此前共有偶数个元素）：num先进入small，small顶部会挤出最大的一个元素，加入到big中，这样就维护了small中的元素总小于big中的元素，且big的size比small的size大1。
②大跟堆small的size大于小根堆big的size时（此前共有奇数个元素）：num先进入big，big顶部挤出最小的一个元素，加入small中，这样就维护了big中的元素总大于smalll中的元素，且big的size等于small的size。
priority_queue<int,vector<int>,less<int>>small;
priority_queue<int,vector<int>,greater<int>>big;
void addNum(int num) {
if(small.size()==big.size()){
small.push(num);
big.push(small.top());
small.pop();
}
else{
big.push(num);
small.push(big.top());
big.pop();
}
}访问中位数可以直接以O(1)的速度进行：
double findMedian() {
if(big.size()==small.size())return (big.top()+small.top())/2.0;
else return big.top();
}这是考虑中位数的情况，如果我们维护第k大/小，可以固定一侧堆大小为k，另一侧储存其余元素与其对顶。
复杂度
时间复杂度: O(logn)
空间复杂度: O(n)
复杂度分析：
时间分析：{
考虑堆排序时间复杂度：O(nlogn)。
每次对顶堆的插入操作只插入一个元素，将n均摊至1，故为logn。（插入n个元素达到nlogn）
另外，对顶堆的查询操作时间复杂度：O(1)。
}
Code
class MedianFinder {
priority_queue<int,vector<int>,less<int>>small;
priority_queue<int,vector<int>,greater<int>>big;
public:
MedianFinder() {}
void addNum(int num) {
if(small.size()==big.size()){
small.push(num);
big.push(small.top());
small.pop();
}
else{
big.push(num);
small.push(big.top());
big.pop();
}
}
double findMedian() {
if(big.size()==small.size())return (big.top()+small.top())/2.0;
else return big.top();
}
};原文地址：https://blog.csdn.net/dakingffo/article/details/142892436
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！