LeetCode Hot 100 —— 堆

堆的概念

堆（heap）是一种特殊的完全二叉树，常用来快速找到“最大值”或“最小值”。

堆分两种：
大顶堆：每个父节点都 >= 它的子节点
所以根节点一定是最大值
小顶堆：每个父节点都 <= 它的子节点
所以根节点一定是最小值

215. 数组中的第K个最大元素

基于快速排序的选择方法

思路和算法

可以用快速排序来解决这个问题，先对原数组排序，再返回倒数第 k 个位置，这样平均时间复杂度是O(nlogn)，但其实我们可以做的更快。

首先我们来回顾一下快速排序，是一种高效、常用、分治法的排序算法。我们对数组a[l⋯r]做快速排序的过程是：

分解：选一个基准数，将数组 a[l⋯r]「划分」成两个子数组 a[l⋯q−1]、a[q+1⋯r]，使得 a[l⋯q−1] 中的每个元素小于等于 a[q]，且 a[q] 小于等于 a[q+1⋯r] 中的每个元素。其中，计算下标 q 也是「划分」过程的一部分。
解决：通过递归调用快速排序，再对左右两边的子数组 a[l⋯q−1] 和 a[q+1⋯r] 进行递归排序。
合并：因为子数组都是原址排序的，所以不需要进行合并操作，a[l⋯r] 已经有序。

上文中提到的划分过程是：从子数组 a[l⋯r] 中选择任意一个元素 x 作为主元，调整子数组的元素使得左边的元素都小于等于它，右边的元素都大于等于它。
由此可以发现每次经过「划分」操作后，我们一定可以确定一个元素的最终位置，即 x 的最终位置为 q，并且保证 a[l⋯q−1] 中的每个元素小于等于 a[q]，且 a[q] 小于等于 a[q+1⋯r] 中的每个元素。所以只要某次划分的 q 为倒数第 k 个下标的时候，我们就已经找到了答案。

因此我们可以改进快速排序算法来解决这个问题：在分解的过程当中，我们会对子数组进行划分，如果划分得到的 q 正好就是我们需要的下标，就直接返回 a[q]；否则，如果 q 比目标下标小，就递归右子区间，否则递归左子区间。这样就可以把原来递归两个区间变成只递归一个区间，提高了时间效率。这就是快速选择算法。

我们知道快速排序的性能和划分出的子数组的长度密切相关。直观地理解，如果每次规模为 n 的问题我们都划分成 1 和 n−1，每次递归的时候又向 n−1 的集合中递归，这种情况是最坏的，时间代价是 O(n^2)。我们可以引入随机化来加速这个过程，它的时间代价的期望是 O(n)。

需要注意的是，这个时间复杂度只有在随机数据下才成立，而对于精心构造的数据则可能表现不佳。因此我们这里并没有真正地使用随机数，而是使用双指针的方法，这种方法能够较好地应对各种数据。

思路简练地概括成这样：

递归三部曲：
1、确定递归函数的参数和返回值
快速排序核心函数：int quickselect(vector<int> &nums, int l, int r, int k)

参数含义：
nums：原数组
l：当前查找区间左边界
r：当前查找区间右边界
k：目标下标，所以返回值直接是nums[k]

2、确定终止条件

if(l==r)returnnums[k];

如果当前区间只剩下一个元素，那这个元素就是答案。

3、确定单层递归的逻辑

核心代码：

classSolution{public:intquickSelect(vector<int>&nums,intl,intr,intk){if(l==r){returnnums[k];}inti=l;//左指针指向左边界intj=r;//右指针指向右边界intpivot=nums[(l+r)/2];//先取要判断的元素为中值while(i<=j){while(nums[i]<pivot)i++;while(nums[j]>pivot)j--;//此时左右指针都指向了第一个不满足顺序的元素if(i<=j){swap(nums[i],nums[j]);i++;j--;}}// 循环结束后：[l, j] 中的元素 <= pivot, [i, r] 中的元素 >= pivot，重要！！！！！// 中间可能有一段元素 == pivot//循环结束时, j是左半边最后一个元素的位置, i是右半边第一个元素的位置if(k<=j)returnquickSelect(nums,l,j,k);if(k>=i)returnquickSelect(nums,i,r,k);returnnums[k];//k落在中间等于 pivot 的区域，注意这里k是指索引为k的元素}intfindKthLargest(vector<int>&nums,intk){intn=nums.size();returnquickSelect(nums,0,n-1,n-k);//注意第k大是n-k！}};

【注】
1、循环结束后：[l, j] 中的元素 <= pivot, [i, r] 中的元素 >= pivot，重要！！！！！

2、int quickSelect(vector<int>& nums, int l, int r, int k)
这里k是索引为k的元素
quickSelect函数是找到索引为k的元素，而题目要求是找到第k大，所以是n-k
quickSelect(nums,0,n-1,n-k);由于要找到第k大，所以是n-k

法二：
用堆来做

classSolution{public:intfindKthLargest(vector<int>&nums,intk){// 使用大顶堆存储所有元素priority_queue<int>heap;//默认是大顶堆！// 将数组元素加入大根堆for(intnum:nums){heap.push(num);}// 弹出前 k - 1 大的元素for(inti=1;i<k;i++){heap.pop();}// 堆顶元素就是第 k 大的元素returnheap.top();}};

ACM：

#include<iostream>#include<vector>#include<algorithm>usingnamespacestd;classSolution{public:intquickSelect(vector<int>&nums,intl,intr,intk){if(l==r){returnnums[k];}inti=l;//左指针指向左边界intj=r;//右指针指向右边界intpivot=nums[(l+r)/2];//先取要判断的元素为中值while(i<=j){while(nums[i]<pivot)i++;while(nums[j]>pivot)j--;//此时左右指针都指向了第一个不满足顺序的元素if(i<=j){swap(nums[i],nums[j]);i++;j--;}}// 循环结束后：[l, j] 中的元素 <= pivot, [i, r] 中的元素 >= pivot// 中间可能有一段元素 == pivot//循环结束时, j是左半边最后一个元素的位置, i是右半边第一个元素的位置if(k<=j)returnquickSelect(nums,l,j,k);if(k>=i)returnquickSelect(nums,i,r,k);returnnums[k];//k落在中间等于 pivot 的区域}intfindKthLargest(vector<int>&nums,intk){intn=nums.size();returnquickSelect(nums,0,n-1,n-k);}};intmain(){intn,k;cin>>n>>k;vector<int>nums(n);for(inti=0;i<n;i++)cin>>nums[i];Solution solution;cout<<solution.findKthLargest(nums,k)<<endl;return0;}

347. 前k个高频元素

首先统计元素出现的频率，这一类的问题可以使用map来进行统计（key存放元素，value存放元素出现次数）。
没有必要对所有元素进行排序，只需要维护k个有序的集合就可以了（因为求频率前k高的）。选用大顶堆和小顶堆来实现。

大顶堆和小顶堆是堆（Heap）这种数据结构的两种主要形式。它们都是特殊的完全二叉树，但在节点的排序方式上刚好相反。
大顶堆中根节点（堆顶）是整个堆中最大的元素。从堆顶往下，路径上的元素是递减的（非严格递减）。
小顶堆中根节点（堆顶）是整个堆中最小的元素。从堆顶往下，路径上的元素是递增的（非严格递增）。

注意：
大顶堆的应用：
维护前 k 个最小元素，因为pop出的是根节点（是最大的）
小顶堆的应用：
维护前 k 个最大元素
所以这里用小顶堆。

对频率进行排序，这里我们可以使用一种容器适配器就是优先级队列(priority_queue)。什么是优先级队列呢？
其实就是一个披着队列外衣的堆，因为优先级队列对外接口只是从队头取元素，从队尾添加元素，再无其他取元素的方式，看起来就是一个队列。

而且优先级队列内部元素是自动依照元素的权值排列。那么它是如何有序排列的呢？
大顶堆、小顶堆是实现优先级队列的常用底层结构。
缺省情况下priority_queue利用max-heap（大顶堆）完成对元素的排序，这个大顶堆是以vector为表现形式的complete binary tree（完全二叉树）。
所以大家经常说的大顶堆（堆头是最大元素），小顶堆（堆头是最小元素），如果懒得自己实现的话，就直接用priority_queue（优先级队列）就可以了，底层实现都是一样的。

代码思路：先使用unordered_map统计每个数字出现的频率。然后利用小顶堆维护频率最高的 K 个元素。

一、priority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison> pri_que;
priority_queue 本质上是一个类模板。C++中需要做到“同一套逻辑，能装任意类型，并且还能自定义排序规则/底层容器”。要达到这个“泛型”，最直接的机制就是类模板。可以理解为：priority_queue不是一个具体类名，而是一个“类的生成器”。你给它模板参数，它才变成某个具体类型的队列。
例如：

priority_queue<int>a;priority_queue<pair<int,int>,vector<pair<int,int>>,mycomparison>b;

priority_queue<int> a;后两个参数用默认值。

1、T（元素类型）：pair<int, int>
队列里每个元素长这样：{key, freq}（你代码里是 {数字, 出现次数}）

2、Container（底层容器类型）：vector<pair<int, int>>
priority_queue 内部实际是用一个 vector 来存数据，然后用堆算法维护顺序
这里就是“用 vector 存 pair”

3、Compare（比较器类型）：mycomparison类，在类里重载()
决定“谁应该在堆顶”的规则
因为默认情况下priority_queue利用max-heap（大顶堆）完成对元素的排序，所以要重载（）。你写的 operator() 让它按 second（频率）比较，从而实现按频率排序的小顶堆。

为何重载（）就实现了重新定义比较逻辑？
因为priority_queue 内部会保存一个 Compare comp;，并在调整堆（push/pop）时反复调用comp(x, y)来决定谁该在上面。

整体思路：
自定义小顶堆排序规则（定义一个class，重载（））—— 使用unordered_map统计——使用小顶堆排序
——收集结果

classSolution{public:// 小顶堆classmycomparison{public:booloperator()(constpair<int,int>&lhs,constpair<int,int>&rhs){returnlhs.second>rhs.second;//比较unordered_map中的第二个参数，即值}};vector<int>topKFrequent(vector<int>&nums,intk){// 要统计元素出现频率unordered_map<int,int>map;// map<nums[i],对应出现的次数>for(inti=0;i<nums.size();i++){map[nums[i]]++;}// 对频率排序// 定义一个小顶堆，大小为kpriority_queue<pair<int,int>,vector<pair<int,int>>,mycomparison>pri_que;// 用固定大小为k的小顶堆，扫描所有频率的数值for(autoit=map.begin();it!=map.end();it++){pri_que.push(*it);if(pri_que.size()>k){// 如果堆的大小大于k了，则队列弹出，保证堆的大小一直为kpri_que.pop();//排序规则在bool operator()里定义了！！}}// 找出前K个高频元素，因为小顶堆先弹出的是k个高频元素中最小的，所以倒序来输出到数组vector<int>result(k);for(inti=k-1;i>=0;i--){result[i]=pri_que.top().first;pri_que.pop();}returnresult;}};

【注】
0、lhs 参数是一个 pair 对象的引用，所以访问成员要用 . 而 -> 只能用在指针/迭代器上。
1、重载()时，const T& 是最标准、最安全的写法，希望比较过程是纯比较，不改数据。
2、比较运算在建堆时是如何应用的，为什么左大于右就会建立小顶堆，反而建立大顶堆？
在 priority_queue/堆算法里，Compare 不是“谁更大谁优先”，而是“a 是否应该排在 b 前面（a 的优先级是否更低/更靠后）”的规则。
堆算法维持的是：父节点不能“ ”子节点
comp = less（<）→ 父不能小于子 → 大顶堆
comp = greater（>）→ 父不能大于子 → 小顶堆
3、map[nums[i]]意思是：用 nums[i] 当key去查 unordered_map 里对应的 value，并返回这个 value 的“引用”（可以修改）。
4、
unordered_map<int,int>：你告诉它key类型、value类型即可，pair是它内部自动组合的。
priority_queue<pair<int,int>>：你需要明确告诉它每个元素长什么样，而你要“两个值一起存”，所以元素类型就得是 pair。

5、pri_que.push(*it);
it 是unordered_map<int,int>::iterator，解引用 *it 得到的是一条“键值对”：
*it 的类型是：std::pair<const int, int>
first：key（数字），是const int（map的key不能被改）
second：value（次数），是int
更直观写法：pri_que.push({it->first, it->second});

7、priority_queue常用操作函数
push(x)：插入元素
top()：取堆顶元素（不删除）
pop()：删除堆顶元素
size()：元素个数
empty()：是否为空

8、vector<int> result(k);
后面是按下标直接赋值，所以(k)是必须的

9、for (int i = k - 1; i >= 0; i--) {i >= 0别忘了=

ACM:

#include<iostream>#include<queue>#include<vector>#include<unordered_map>usingnamespacestd;classComparison{public:booloperator()(constpair<int,int>&a,constpair<int,int>&b){returna.second>b.second;}};vector<int>FindK(vector<int>&vec,intk){unordered_map<int,int>map;for(inti=0;i<vec.size();i++){map[vec[i]]++;}priority_queue<pair<int,int>,vector<pair<int,int>>,Comparison>que;for(autoit=map.begin();it!=map.end();it++){que.push(*it);if(que.size()>k){que.pop();}}vector<int>res(k);for(inti=0;i<k;i++){res[i]=que.top().first;que.pop();}returnres;}intmain(){intn,k;cin>>n>>k;vector<int>nums(n);for(inti=0;i<n;i++){cin>>nums[i];}vector<int>res=FindK(nums,k);for(inti=0;i<k;i++){cout<<res[i];if(i!=k-1)cout<<" ";}cout<<endl;return0;}

295. 数据流的中位数

它的核心思想是用两个堆维护两半数据：
① 定义大小顶堆
left：大顶堆，存较小的一半，堆顶是这半里最大的（最大的要push出去到右边，所以用大顶堆）
right：小顶堆，存较大的一半，堆顶是这半里最小的

②addNum:
添加元素时，先放入大顶堆，再将大顶堆堆顶移动到小顶堆；
如果小顶堆（right）元素比大顶堆（left）多，则从小顶堆弹出一个最小元素到大顶堆，确保平衡。

③findMedian:
这样中位数就很好取：
如果总数是奇数：中位数就是 left.top()
如果总数是偶数：中位数就是 left.top() 和 right.top() 的平均值

核心代码：

classMedianFinder{public:priority_queue<int>left;//默认大顶堆priority_queue<int,vector<int>,greater<int>>right;MedianFinder(){}voidaddNum(intnum){left.push(num);intres=left.top();right.push(res);left.pop();if(right.size()>left.size()){left.push(right.top());right.pop();}}doublefindMedian(){if(left.size()>right.size())returnleft.top();return(left.top()+right.top())/2.0;}};

【注】
1、return (left.top( )+right.top( ))/2.0;
注意/2.0 因为要保留一位小数

2、priority_queue<int, vector<int>, greater<int>> right;注意第一个是int，不是<int>

ACM：

#include<vector>#include<queue>#include<iostream>#include<string>#include<iomanip>usingnamespacestd;classMedianFinder{public:priority_queue<int>left;//默认大顶堆priority_queue<int,vector<int>,greater<int>>right;MedianFinder(){}voidaddNum(intnum){left.push(num);intres=left.top();right.push(res);left.pop();if(right.size()>left.size()){left.push(right.top());right.pop();}}doublefindMedian(){if(left.size()>right.size())returnleft.top();return(left.top()+right.top())/2.0;}};intmain(){intq;cin>>q;MedianFinder mf;while(q--){string s;cin>>s;if(s=="add"){intx;cin>>x;mf.addNum(x);}elseif(s=="median"){cout<<fixed<<setprecision(1)<<mf.findMedian()<<endl;}}return0;}

【注】
1、cout << fixed << setprecision(1) << mf.findMedian() <<endl;
固定保留1 位小数
要包含头文件#include <iomanip>
fixed
表示用普通小数形式输出，而不是科学计数法。

setprecision(1)
表示：保留 1 位小数。