【优选算法 | 优先级队列】从堆实现到解题框架：彻底搞懂优先级队列
优先级队列（Priority Queue），本质上是一个支持动态插入与按优先级弹出操作的堆结构，是处理这类问题的强力工具。
本文将从底层的堆实现出发，逐步构建出优先级队列的完整解题框架，并结合高频
题目，帮助你真正掌握它在算法实战中的运用。
🌈个人主页：是店小二呀
🌈C/C++专栏：C语言\\ C++
🌈初/高阶数据结构专栏： 初阶数据结构\\ 高阶数据结构
🌈Linux专栏： Linux
🌈算法专栏：算法
🌈Mysql专栏:Mysql
🌈你可知:无人扶我青云志 我自踏雪至山巅
文章目录
- 一、铺垫知识
-
- 1.1 堆排序（Heap Sort）
- 1.2 快速选择（QuickSelect）算法解决 Top K 问题
- 3.在Tok问题，什么时候使用大根堆和小根堆？
- 1046. 最后一块石头的重量
- 703. 数据流中的第 K 大元素
- 692. 前K个高频单词
- 295. 数据流的中位数
本专题利用优先级队列来解决问题。为此，我们首先需要了解如何使用堆和快速选择算法来解决 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. 最后一块石头的重量
【算法思路】
利用堆的特性，反复取出当前最大值和次大值进行碰撞处理，然后将结果重新插入堆中。
【代码实现】
class Solution {public: int lastStoneWeight(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 大元素。
【代码实现】
class KthLargest {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(); } } int add(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 个高频元素。
【代码实现】
class Solution {public: typedef pair<string, int> PSI; struct Cmp { bool operator()(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 时，放入大根堆，否则放入小根堆。然后根据这两个准则和两个堆的数量关系，进行适当的调整和维护。
【代码实现】
class MedianFinder {public: priority_queue<int> left;//大根堆 priority_queue<int,vector<int>, greater<int>> right;//小根堆 MedianFinder() { } void addNum(int num) { if(left.size() == right.size()) { if(left.size() == 0 || num <= left.top()) left.push(num); else if(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(); } else if(num > left.top()) right.push(num); } } double findMedian() { if(left.size() == right.size()) return ((left.top() + right.top()) / 2.0); else return left.top(); }};【细节问题】
为了避免在访问 left.top() 时出现非法访问，我们应该首先检查 left 大根堆是否为空。具体来说，条件 left.size() == 0 || num <= left.top() 确保只有在堆非空且 num 小于等于堆顶元素时，才执行相关操作。
快和小二一起踏上精彩的算法之旅！关注我，我们将一起破解算法奥秘，探索更多实用且有趣的知识，开启属于你的编程冒险！
