【优选算法 | 优先级队列】从堆实现到解题框架：彻底搞懂优先级队列
| 算法 | 相关知识点 | 可以通过点击 | 以下链接进行学习 | 一起加油！ |
|---|---|---|---|---|
| 双指针 | 滑动窗口 | 二分查找 | 前缀和 | 位运算 |
| 模拟 | 链表 | 哈希表 | 字符串模拟 | 栈模拟(非单调栈) |
优先级队列（Priority Queue），本质上是一个支持动态插入与按优先级弹出操作的堆结构，是处理这类问题的强力工具。
本文将从底层的堆实现出发，逐步构建出优先级队列的完整解题框架，并结合高频
题目，帮助你真正掌握它在算法实战中的运用。
🌈个人主页：是店小二呀
🌈C/C++专栏：C语言\ C++
🌈初/高阶数据结构专栏： 初阶数据结构\ 高阶数据结构
🌈Linux专栏： Linux
🌈算法专栏：算法
🌈Mysql专栏:Mysql
🌈你可知:无人扶我青云志 我自踏雪至山巅
文章目录
本专题利用优先级队列来解决问题。为此，我们首先需要了解如何使用堆和快速选择算法来解决 Tok 问题，并掌握大根堆与小根堆的适用场景及选择依据。
一、铺垫知识
1.1 堆排序（Heap Sort）
堆排序使用 最大堆（Max Heap） 或 最小堆（Min Heap） 来实现排序。
具体可以参考这篇文章:理解堆的哇塞大碗大碗吗。 ， ，/，/ 发 的特性与应用
1.2 快速选择（QuickSelect）算法解决 Top K 问题
如果你使用 选择排序 来解决 Top K（Tok）问题，实际上不需要对整个数组进行完整排序，而是只运行 K 次选择过程 来找到 第 K 大（或 K 小）元素。
具体可以参考这篇文章:七大常见排序
3.在Tok问题，什么时候使用大根堆和小根堆？
大根堆（Max Heap）：用于获取最大元素或 Top K 最小元素（维持 K 个最小元素，堆顶最大）。示例：找 前 K 小（维护大小为 K 的大根堆）。小根堆（Min Heap）：用于获取最小元素或 Top K 最大元素（维持 K 个最大元素，堆顶最小）。示例：找 前 K 大（维护大小为 K 的小根堆）。
1046. 最后一块石头的重量
【题目】：1046. 最后一块石头的重量
【算法思路】
利用堆的特性，反复取出当前最大值和次大值进行碰撞处理，然后将结果重新插入堆中。
【代码实现】
classSolution{public:intlastStoneWeight(vector<int>& stones){int n = stones.size(); priority_queue<int> head;for(auto x: stones) head.push(x);while(head.size()>1){int x = head.top(); head.pop();int y = head.top(); head.pop();if(x > y) head.push(x - y);}return head.size()? head.top():0;}};703. 数据流中的第 K 大元素
【题目】：703. 数据流中的第 K 大元素
【算法思路】
该题主要考察 Top K 问题的处理方法。为了查找第 K 大元素，我们使用小根堆。当插入新元素时，如果堆的大小超过 K，就会移除堆顶元素（即最小值）。
每次插入时，堆会自动调整，保持堆顶为当前 K 个最大元素中的最小值。如果插入的元素大于堆顶，则替换堆顶元素；如果小于堆顶，则保持堆不变。通过这种方式，堆会动态维护第 K 大元素。
【代码实现】
classKthLargest{public: priority_queue<int, vector<int>, greater<int>> heap;int _k;KthLargest(int k, vector<int>& nums){ _k = k;for(auto x : nums){ heap.push(x);if(heap.size()> _k) heap.pop();}}intadd(int val){ heap.push(val);if(heap.size()> _k) heap.pop();return heap.top();}};692. 前K个高频单词
【题目】：692. 前K个高频单词
【算法思路】
本题明确要求使用堆来解决 Top K 问题，接下来我们分析其算法思路
要使用堆来解决 Top K 问题，需要根据题目要求选择合适的堆结构。这里有两种排序策略：
频次:小根堆
- 按频次排序：使用小根堆，确保堆顶始终是当前 K 个元素中频次最低的。
- 按字典序排序（当频次相同时）：使用大根堆，保证相同频次下按字典序降序排列。
由于字典序排序是频次排序的子集，我们可以在比较函数中添加 if 语句，灵活实现多条件排序。最终结果需要倒序遍历，因为答案要求按照单词出现频率从高到低排序，因此我们使用小根堆来维护前 K 个高频元素。
【代码实现】
classSolution{public:typedef pair<string,int> PSI;structCmp{booloperator()(const PSI & a,const PSI & b){if(a.second == b.second){return a.first < b.first;}return a.second > b.second;}}; vector<string>topKFrequent(vector<string>& words,int k){//1.统计单词出现次数 unordered_map<string,int> hash;for(auto& str : words) hash[str]++;//2.创建一个大小为 k 的堆(存储频率) priority_queue<PSI, vector<PSI>, Cmp> heap;//3.Tok逻辑for(auto& psi : hash){ heap.push(psi);if(heap.size()> k) heap.pop();}//4.提取结果 vector<string>ret(k);for(int i = k -1; i >=0; i--){ ret[i]= heap.top().first; heap.pop();}return ret;}};295. 数据流的中位数
【题目】：295. 数据流的中位数
【算法思路】
由于数据量庞大，前两种解法可能会超时。接下来介绍一种优化解法，虽然不太容易直接想到，但学会后会觉得非常简单。这个方法与栈用于括号匹配或出栈队列类似，思路是用大小堆来维护数据流的中位数。遇到类似问题时，可以考虑使用这种思路。
解法三：大小堆来维护数据流的中位数
根据准则 m == n 和 m > n (m == n + 1)，我们根据 num 的值进行分类讨论。当 num < x 时，放入大根堆，否则放入小根堆。然后根据这两个准则和两个堆的数量关系，进行适当的调整和维护。
【代码实现】
classMedianFinder{public: priority_queue<int> left;//大根堆 priority_queue<int,vector<int>, greater<int>> right;//小根堆MedianFinder(){}voidaddNum(int num){if(left.size()== right.size()){if(left.size()==0|| num <= left.top()) left.push(num);elseif(num > left.top()){ right.push(num); left.push(right.top()); right.pop();}}else{if(num <= left.top()){ left.push(num); right.push(left.top()); left.pop();}elseif(num > left.top()) right.push(num);}}doublefindMedian(){if(left.size()== right.size())return((left.top()+ right.top())/2.0);elsereturn left.top();}};【细节问题】
为了避免在访问 left.top() 时出现非法访问，我们应该首先检查 left 大根堆是否为空。具体来说，条件 left.size() == 0 || num <= left.top() 确保只有在堆非空且 num 小于等于堆顶元素时，才执行相关操作。
快和小二一起踏上精彩的算法之旅！关注我，我们将一起破解算法奥秘，探索更多实用且有趣的知识，开启属于你的编程冒险！
