C++ 中的优先级队列（Priority Queue）是一种容器适配器，它提供队列的功能，但元素不是按照插入的顺序被访问，而是根据它们的优先级被访问。默认情况下，优先级队列是一个最大堆（Max-Heap），这意味着队列的根元素总是优先级最高的元素（即值最大的元素）。不过，你也可以通过自定义比较函数来改变这个行为，使其变成最小堆（Min-Heap）。
1.基本用法
在 C++ 中，优先级队列通常通过 <queue> 头文件来使用。下面是一个简单的例子，展示了如何声明和使用优先级队列：
#include <iostream>
#include <queue>
#include <vector>
int main() {
// 创建一个默认的最大堆优先级队列
std::priority_queue<int> pq;
// 向队列中添加元素
pq.push(10);
pq.push(20);
pq.push(15);
// 访问并移除最高优先级的元素
while (!pq.empty()) {
std::cout << pq.top() << " "; // 输出最大元素
pq.pop(); // 移除最大元素
}
std::cout << std::endl;
return 0;
}
输出将是：
20 15 102.自定义优先级
如果想创建一个最小堆或者基于自定义比较逻辑的优先级队列，可以使用模板参数来指定比较函数或比较对象。例如：
小根堆：
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
int main()
{
priority_queue<int, vector<int>, greater<int>> qe;
qe.push(4);
qe.push(2);
qe.push(1);
while (!qe.empty())
{
int a = qe.top();
cout << a << ", ";
qe.pop();
}
return 0;
}自定义比较逻辑：
#include <iostream>
#include <queue>
#include <vector>
#include <functional> // std::greater
struct Custom {
int id;
std::string name;
// 重载小于运算符以用于最小堆
bool operator<(const Custom& other) const {
return id > other.id; // 注意这里是大于，因为我们想要最小堆
}
};
int main() {
// 创建一个最小堆优先级队列
std::priority_queue<Custom, std::vector<Custom>, std::greater<Custom>> pq;
pq.push({3, "Alice"});
pq.push({1, "Bob"});
pq.push({2, "Charlie"});
while (!pq.empty()) {
Custom top = pq.top();
std::cout << "ID: " << top.id << ", Name: " << top.name << std::endl;
pq.pop();
}
return 0;
}
在这个例子中，我们定义了一个 Custom 结构体，并通过重载小于运算符 operator< 来创建一个最小堆。我们还使用了 std::greater<Custom> 作为第三个模板参数来显式指定比较函数。
3.注意事项
- 效率：优先级队列的插入和删除操作（
push和pop）的时间复杂度通常为 O(log n)，其中 n 是队列中元素的数量。 - 排序稳定性：由于优先级队列是基于堆实现的，因此它并不保证相同优先级的元素按照它们被插入的顺序来访问。
- 自定义类型：当使用自定义类型时，确保提供了必要的比较逻辑（如重载
operator<或提供比较函数对象）。
通过了解这些基本概念和用法，可以有效地利用 C++ 的优先级队列来解决需要优先级处理的问题。
4.例题
1.最后一块石头的重量
有一堆石头，每块石头的重量都是正整数。
每一回合，从中选出两块 最重的 石头，然后将它们一起粉碎。假设石头的重量分别为 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]，这就是最后剩下那块石头的重量。
解法(利用堆)
算法思路:
其实就是一个模拟的过程:
- 每次从石堆中拿出最大的元素以及次大的元素，然后将它们粉碎;
- 如果还有剩余，就将剩余的石头继续放在原始的石堆里面。
重复上面的操作，直到石堆里面只剩下一个元素，或者没有元素(因为所有的石头可能全部抵消了)
那么主要的问题就是解决:
- 如何顺利的拿出最大的石头以及次大的石头;
- 并且将粉碎后的石头放入石堆中之后，也能快速找到下一轮粉碎的最大石头和次大石头;
这不正好可以利用堆的特性来实现嘛?
- 我们可以创建一个大根堆;
- 然后将所有的石头放入大根堆中;
- 每次拿出前两个堆顶元素粉碎一下，如果还有剩余，就将剩余的石头继续放入堆中；
这样就可以快速模拟出整个过程。
class Solution {
public:
int lastStoneWeight(vector<int>& stones)
{
priority_queue<int> qe;//默认创建时是大根堆
for(int i=0;i<stones.size();i++)
{
qe.push(stones[i]);
}
int a=0;
while(qe.size()>1)
{
int x=qe.top();//取出堆顶元素
qe.pop();
int y=qe.top();
qe.pop();
if(x!=y)
{
a=max(x,y)-min(x,y);
qe.push(a);
}
}
if(qe.size()==1)
return qe.top();
else
return 0;
}
};2.数据流中的第 K 大元素
设计一个找到数据流中第 k 大元素的类（class）。注意是排序后的第 k 大元素，不是第 k 个不同的元素。
请实现 KthLargest 类：
KthLargest(int k, int[] nums)使用整数k和整数流nums初始化对象。int add(int val)将val插入数据流nums后，返回当前数据流中第k大的元素。
示例 1：
输入：
["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); // 返回 4
kthLargest.add(5); // 返回 5
kthLargest.add(10); // 返回 5
kthLargest.add(9); // 返回 8
kthLargest.add(4); // 返回 8
解法（优先级队列)
这是经典的TopK问题。我们常用堆排序来解决问题。对于TopK问题，如果要求前K个最大的元素，可以维护一个小顶堆；如果要求前K个最小的元素，可以维护一个大顶堆。具体步骤如下：
- 用数据集合中前K个元素来建堆。
- 用剩余的N-K个元素依次与堆顶元素来比较，如果比堆顶的数据大（对于求前K个最大元素的情况），就替换它进堆，并调整堆结构。
- 将剩余N-K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素。
堆排序法的时间复杂度为O(nlogk)，其中n是数据的个数，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();
}
};3.前K个高频单词
给定一个单词列表 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 次。
解法(堆)
算法思路
稍微处理一下原数组:
a.我们需要知道每一个单词出现的频次，因此可以先使用哈希表，统计出每一个单词出现的频次;
b.然后在哈希表中，选出前k大的单词(为什么不在原数组中选呢?因为原数组中存在重复的单词，哈希表里面没有重复单词，并且还有每一个单词出现的频次)
如何使用堆，拿出前k大元素:
a.先定义一个自定义排序，我们需要的是前k大，因此需要一个小根堆。但是当两个字符串的频次相同的时候，我们需要的是字典序较小的，此时是一个大根堆的属性，在定义比较器的时候需要注意!
- 当两个字符串出现的频次不同的时候:需要的是基于频次比较的小根堆
- 当两个字符串出现的频次相同的时候:需要的是基于字典序比较的大根堆
b.定义好比较器之后，依次将哈希表中的字符串插入到堆中，维持堆中的元素不超过 k 个;
c.遍历完整个哈希表后，堆中的剩余元素就是前 k大的元素
class Solution {
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;
}
};
public:
vector<string> topKFrequent(vector<string>& words, int k)
{
//1.统计一下每个单词的频次
unordered_map<string,int> hash;
for(auto &s:words)
{
hash[s]++;
}
//2.建堆
priority_queue<psi,vector<psi>,cmp> heap;
//3.TopK的逻辑
for(auto& x:hash)
{
heap.push(x);
if(heap.size()>k)
heap.pop();
}
//4.提取结果
vector<string> vv(k);
for(int i=k-1;i>=0;i--)
{
vv[i]=heap.top().first;
heap.pop();
}
return vv;
}
};4.数据流的中位数
中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。
- 例如
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
解法(利用两个堆)
算法思路:
这是一道关于「堆」这种数据结构的一个「经典应用」。我们可以将整个数组「按照大小」平分成两部分(如果不能平分，那就让较小部分的元素多一个)较小的部分称为左侧部分，较大的部分称为右侧部分:
- 将左侧部分放入「大根堆」中，然后将右侧元素放入「小根堆入中;
- 这样就能在 O(1)的时间内拿到中间的一个数或者两个数，进而求的平均数。
于是问题就变成了「如何将一个一个从数据流中过来的数据，动态调整到大根堆或者小根堆中，并且保证两个堆的元素一致，或者左侧堆的元素比右侧堆的元素多一个」
为了方便叙述，将左侧的「大根堆」记为 left ，右侧的「小根堆」记为 right ，数据流中来的
「数据」记为 x。
其实，就是一个「分类讨论」的过程:
1. 如果左右堆的「数量相同」，left.size()== right.size():
a.如果两个堆都是空的，直接将数据x放入到 left中;
b.如果两个堆非空
i.如果元素要放入左侧，也就是x<= left.top():那就直接放，因为不会影响我们制定的规则;
ii.如果要放入右侧
可以先将 x放入 right 中,
然后把 right 的堆顶元素放入 left中;
2.如果左右堆的数量「不相同」，那就是 left.size()>right.size():
a.这个时候我们关心的是 x是否会放入 left 中，导致 left 变得过多:
i.如果 x放入 right 中，也就是x>= right.top()，直接放;
ii.反之，就是需要放入 left 中:
可以先将 x放入 left 中，
然后把 left 的堆顶元素放入 right中
只要每一个新来的元素按照「上述规则」执行，就能保证 left 中放着整个数组排序后的「左半部分」，right 中放着整个数组排序后的「右半部分」，就能在 0(1)的时间内求出平均数。
class MedianFinder {
priority_queue<int> left;//大根堆
priority_queue<int,vector<int>,greater<int>> right;//小根堆
public:
MedianFinder()
{}
void addNum(int num)
{
int m=left.size();
int n=right.size();
//分类讨论
if(m==n)
{
if(m==0)//为空直接放入左边大根堆
{
left.push(num);
}
else
{
if(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();
else
{
return (left.top()+right.top())/2.0;
}
}
};
