优先队列（Priority Queue）是一种抽象数据类型，它类似于队列（Queue），但是每个元素都有一个关联的优先级。在优先队列中，元素按照优先级从高到低（或从低到高）排列，高优先级的元素先出队。这种数据结构可以用堆（Heap）来实现。
堆是一种二叉树结构，有两种主要类型：最大堆和最小堆。在最大堆中，每个节点的值都大于或等于其子节点的值；而在最小堆中，每个节点的值都小于或等于其子节点的值。对于优先队列来说，最大堆常常用于实现。
在堆中，根节点的元素具有最高（或最低）优先级，而且这一性质对于整个堆中的每个节点都成立。这确保了当我们从堆中移除元素时，总是移除具有最高（或最低）优先级的元素。
优先队列的常见操作包括：
- 插入（Insertion）：将元素插入队列中。
- 删除最大（或最小）元素：移除并返回队列中具有最高（或最低）优先级的元素。
堆的实现可以通过数组或链表等数据结构。在使用数组实现堆时，父节点和子节点之间的关系可以通过数组的索引关系来表示。在C++中，可以使用 std::priority_queue 来实现优先队列，它默认使用最大堆，也可以通过传递自定义比较函数来实现最小堆。
01.最后一块石头的重量
题目链接：https://leetcode.cn/problems/last-stone-weight/
有一堆石头，每块石头的重量都是正整数。
每一回合，从中选出两块 最重的 石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：
- 如果
x == y，那么两块石头都会被完全粉碎； - 如果
x != y，那么重量为x的石头将会完全粉碎，而重量为y的石头新重量为y-x。
最后，最多只会剩下一块石头。返回此石头的重量。如果没有石头剩下，就返回 0。
示例：
输入：[2,7,4,1,8,1]
输出：1
解释：
先选出 7 和 8，得到 1，所以数组转换为 [2,4,1,1,1]，
再选出 2 和 4，得到 2，所以数组转换为 [2,1,1,1]，
接着是 2 和 1，得到 1，所以数组转换为 [1,1,1]，
最后选出 1 和 1，得到 0，最终数组转换为 [1]，这就是最后剩下那块石头的重量。
提示：
1 <= stones.length <= 301 <= stones[i] <= 1000
思路
我们可以每次拿出最大的两个相比较，有差值就将差值保留，相等就都粉碎，这样我们很容易想到使用堆去计算，因为这符合堆的特性，我们可以使用各语言库中的堆容器来计算。
-
创建最大堆（Max Heap）： 通过
priority_queue<int>创建一个默认为最大堆的优先队列，将给定的石头数组中的元素加入最大堆中。 - 迭代处理： 使用一个循环迭代处理，直到堆中剩余的元素个数小于等于1。
- 从堆中取出两个最大的元素，执行碎石操作： 每次取出堆中的两个最大元素（即石头的重量最大的两块），执行碎石操作，计算碎石后的重量，将结果加回堆中。
- 返回结果： 当循环结束时，堆中剩余的元素即为最后一块石头的重量，或者堆为空，返回相应的结果。
代码文章来源地址https://www.toymoban.com/news/detail-835012.html
class Solution {
public:
int lastStoneWeight(vector<int>& stones) {
priority_queue<int> heap;
for(int x:stones) heap.push(x);
while(heap.size()>1){
int a=heap.top(); heap.pop();
int b=heap.top(); heap.pop();
if(a>b) heap.push(a-b);
}
return heap.size()?heap.top():0;
}
};
02.数据流中的第 K 大元素
题目链接：https://leetcode.cn/problems/kth-largest-element-in-a-stream/
设计一个找到数据流中第 k 大元素的类（class）。注意是排序后的第 k 大元素，不是第 k 个不同的元素。
请实现 KthLargest 类：
-
KthLargest(int k, int[] nums)使用整数k和整数流nums初始化对象。 -
int add(int val)将val插入数据流nums后，返回当前数据流中第k大的元素。
示例：
输入：
["KthLargest", "add", "add", "add", "add", "add"]
[[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]]
输出：
[null, 4, 5, 5, 8, 8]
解释：
KthLargest kthLargest = new KthLargest(3, [4, 5, 8, 2]);
kthLargest.add(3); // return 4
kthLargest.add(5); // return 5
kthLargest.add(10); // return 5
kthLargest.add(9); // return 8
kthLargest.add(4); // return 8
提示：
1 <= k <= 1040 <= nums.length <= 104-104 <= nums[i] <= 104-104 <= val <= 104- 最多调用
add方法104次 - 题目数据保证，在查找第
k大元素时，数组中至少有k个元素
思路
这里是典型的topk问题，找的是第k个大的数，所以我们使用一个k大的小堆就能很好的解决这个问题。
在构造函数中，将初始的元素加入最小堆中，并维护堆的大小为 K，保证堆中只有前 K 大的元素。
当有新元素加入时，将新元素加入最小堆中，然后检查堆的大小是否超过 K，如果超过则弹出堆顶元素。最终返回当前堆顶元素，即为第 K 大的元素。这样，通过不断地将新元素加入最小堆，并保持堆的大小为 K，可以在 add 操作后始终保持堆中的元素为前 K 大的元素，而堆顶元素即为第 K 大的元素。
代码
class KthLargest {
priority_queue<int,vector<int>,greater<int>> heap;
int _k;
public:
KthLargest(int k, vector<int>& nums) {
_k=k;
for(int& 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();
}
};
/**
* Your KthLargest object will be instantiated and called as such:
* KthLargest* obj = new KthLargest(k, nums);
* int param_1 = obj->add(val);
*/
03.前K个高频单词
题目链接：https://leetcode.cn/problems/top-k-frequent-words/
给定一个单词列表 words 和一个整数 k ，返回前 k 个出现次数最多的单词。
返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率， 按字典顺序 排序。
示例 1：
输入: words = ["i", "love", "leetcode", "i", "love", "coding"], k = 2
输出: ["i", "love"]
解析: "i" 和 "love" 为出现次数最多的两个单词，均为2次。
注意，按字母顺序 "i" 在 "love" 之前。
示例 2：
输入: ["the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"], k = 4
输出: ["the", "is", "sunny", "day"]
解析: "the", "is", "sunny" 和 "day" 是出现次数最多的四个单词，
出现次数依次为 4, 3, 2 和 1 次。
注意：
1 <= words.length <= 5001 <= words[i] <= 10-
words[i]由小写英文字母组成。 -
k的取值范围是[1, **不同** words[i] 的数量]
**进阶：**尝试以 O(n log k) 时间复杂度和 O(n) 空间复杂度解决。
思路
很显然这里这是还是topk问题，还是使用堆来解决问题，但是这里有两个比较条件，所以我们要注意比较函数的实现，主逻辑是找出前k个出现次数最多的，所以整体我们建小堆，还有一个附属条件，次数相同时，字典序小的排在前面，所以在相同次数时，我们相对于字符串建大堆，将字母小的排在前面。
-
哈希表统计频率： 使用
unordered_map哈希表记录每个字符串出现的频率。 -
优先队列： 使用一个自定义的比较函数对象
cmp作为优先队列的比较规则。按照频率从大到小排序，若频率相同则按照字符串字典序从小到大排序。遍历哈希表，将每个键值对（字符串及其频率）加入最小堆，并保持堆的大小为 K，当堆的大小超过 K 时，弹出堆顶元素。 - 结果处理： 从堆中依次取出前 K 高的字符串，存储到结果数组中。
最终，返回存储前 K 高字符串的结果数组 ret。这样通过哈希表统计频率，并使用优先队列来维护前 K 高的频率，实现了找出频率前 K 高的字符串。
代码
class Solution {
struct cmp{
bool operator()(const pair<string,int>& a,const pair<string,int>& b){
if(a.second==b.second) return a.first<b.first;
return a.second>b.second;
}
};
public:
vector<string> topKFrequent(vector<string>& words, int k) {
unordered_map<string,int> hash;
for(string& s:words) hash[s]++;
priority_queue<pair<string,int>,vector<pair<string,int>>,cmp> heap;
for(const pair<string,int>& x:hash){
heap.push(x);
if(heap.size()>k) heap.pop();
}
vector<string> ret(k);
for(int i=k-1;i>=0;--i){
ret[i]=heap.top().first;
heap.pop();
}
return ret;
}
};
04.数据流的中位数
题目链接：https://leetcode.cn/problems/find-median-from-data-stream/
中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。
- 例如
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
思路
这里我们最容易想到的暴力解法就是每次插入时排序，但是这种方法时间复杂度太高，其实这里我们可以使用一个大堆和一个小堆来维护所有数，各分一半数据，若两边长度相等，则返回两个堆顶相加除2的值，若不等，返回大堆堆顶即可。
在构造函数中初始化两个优先队列，left 用于存放较小的一半元素（最大堆），right 用于存放较大的一半元素（最小堆）。 在 addNum 方法中，根据元素的大小选择将其插入到左堆或右堆。插入后需要保持两个堆的大小差不超过 1，以确保中位数的计算。 在 findMedian 方法中，根据两个堆的大小关系返回中位数。通过这种方式，不断将数据插入到两个堆中，并保持它们的大小差不超过 1，就能够在 O(1) 时间内查找到当前数据流的中位数。文章来源：https://www.toymoban.com/news/detail-835012.html
代码
class MedianFinder {
priority_queue<int> left;
priority_queue<int,vector<int>,greater<int>> right;
public:
MedianFinder() {}
void addNum(int num) {
if(left.size()==right.size()){
if(left.empty()||num<=left.top()) left.push(num);
else{
right.push(num);
left.push(right.top());
right.pop();
}
}
else{
if(num<=left.top()){
left.push(num);
right.push(left.top());
left.pop();
}else right.push(num);
}
}
double findMedian() {
if(left.size()==right.size()) return (left.top()+right.top())/2.0;
return left.top();
}
};
/**
* Your MedianFinder object will be instantiated and called as such:
* MedianFinder* obj = new MedianFinder();
* obj->addNum(num);
* double param_2 = obj->findMedian();
*/
到了这里，关于算法沉淀——优先级队列(堆)（leetcode真题剖析）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
