一、定义
priority_queue模板
模板输入
1、元素类型
2、容器类型
3、函数对象类型
priority_queue<元素类型, 容器类型, 函数对象类型> qqq;
大顶堆
priority_queue<int> name;
priority_queue默认为大顶堆
故定义也可以写作：priority_queue<int, vector<int>, less<int> > ay;
小顶堆
如果需要构建一个小顶堆，可以改变定义方式为：priority_queue<int, vector<int>, greater<int> > ay;
使用std::greater模板无需自定义比较函数。
自定义比较函数：
#include <queue>
struct Compare {
bool operator()(int a, int b) {
return a > b;
}
};
int main() {
std::priority_queue<int, std::vector<int>, Compare> pq; // 使用自定义的比较函数
pq.push(3);
pq.push(1);
pq.push(2);
while (!pq.empty()) {
std::cout << pq.top() << " ";
pq.pop();
}
return 0;
}
二、接口
优先级队列只能通过top()访问队首元素（优先级最高的那个元素）
pop()：弹出优先级最高的元素
push()：塞元素进队列
empty() size()：是否空和元素个数
#include <iostream>
#include <queue>
using namespace std;
int main() {
priority_queue<int> ay;
ay.push(3);
ay.push(6);
ay.push(2);
cout << ay.top() << endl; // result: 6
ay.pop(); // 弹出6，剩3、2
return 0;
}
三、例子
题目：找出topK的元素
建立 [元素, 元素出现个数] 的键值对
优先级队列中的数据结构为pair<int,int>
将优先级队列的优先级设置为值的小顶堆
定义：priority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison> pri_que;
仿函数mycomparison如下：
class mycomparison {
public:
bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) {
return lhs.second > rhs.second;
}
};
总体：文章来源：https://www.toymoban.com/news/detail-492045.html
class Solution {
public:
// 小顶堆
class mycomparison {
public:
bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) {
return lhs.second > rhs.second;
}
};
vector<int> topKFrequent(vector<int>& nums, int k) {
// 统计元素出现频率
unordered_map<int, int> map;
for (int i = 0; i < nums.size(); i++) {
map[nums[i]]++;
}
priority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison> pri_que;
// 用固定大小为k的小顶堆，扫面所有频率的数值
for (unordered_map<int, int>::iterator it = map.begin(); it != map.end(); it++) {
pri_que.push(*it);
if (pri_que.size() > k) { // 如果堆的大小大于了K，则队列弹出，保证堆的大小一直为k
pri_que.pop();
}
}
vector<int> result(k);
// 倒序
for (int i = k - 1; i >= 0; i--) {
result[i] = pri_que.top().first;
pri_que.pop();
}
return result;
}
};
方法二：
自定义sort函数排序规则文章来源地址https://www.toymoban.com/news/detail-492045.html
class Solution {
public:
static bool compareByValue(const std::pair<int, int>& lhs, const std::pair<int, int>& rhs) {
return lhs.second > rhs.second;
}
vector<int> topKFrequent(vector<int>& nums, int k) {
vector<int> res;
// 要统计元素出现频率
unordered_map<int, int> mymap; // map<nums[i],对应出现的次数>
for (int i = 0; i < nums.size(); i++) {
mymap[nums[i]]++;
}
// 将键值对存储到 vector 中
vector<pair<int, int>> vec(mymap.begin(), mymap.end());
// 使用自定义的比较器函数进行排序
std::sort(vec.begin(), vec.end(), Solution::compareByValue);
// 按照无序容器 unordered_map 中的值来排序
// 遍历输出排序后的键值对
for (int i = 0; i < k; ++i) res.push_back(vec[i].first);
return res;
}
};
四、实现一个优先级队列
#include<iostream>
#include<functional>
#include<string.h>//memecpy
#include<time.h> // time
using namespace std;
//优先级队列实现
class PriorityQueue {
public:
using Comp = function<bool(int, int)>;
PriorityQueue(int cap = 20, Comp comp = greater<int>())
: size_(0)
, cap_(cap)
, comp_(comp) {
que_ = new int[cap_];
}
PriorityQueue(Comp comp)
: size_(0), cap_(20), comp_(comp) {
que_ = new int [cap_];
}
~PriorityQueue() {
delete[] que_;
que_ = nullptr;
}
public:
//入堆操作
void push(int val) {
//判断扩容
if (size_ == cap_) {
int* p = new int[2 * cap_];
memcpy(p, que_, cap_ * sizeof(int));
delete[]que_;
que_ = p;
cap_ *= 2;
}
if (size_ == 0) {
//只有一个元素不用进行堆的上浮调整
que_[size_] = val;
} else {
// 堆里面有多个元素，需要进行上浮调整
siftUp(size_, val);
}
size_++;
}
void pop() {
if (size_ == 0) {
throw "container is empty";
}
size_--;
if (size_ > 0) {
//删除堆顶元素， 还有剩余的元素， 要进行堆的下沉调整
siftDown(0, que_[size_]);
}
}
bool empty() const {
return size_ == 0;
}
int top() const {
if (size_ == 0) {
throw "container is empty!";
}
return que_[0];
}
int size() const {
return size_;
}
private:
//入堆上浮调整 O(log n)
void siftUp(int i, int val) {
while (i > 0) { //最多计算到根节点 0号位
int father = (i - 1) / 2;
if (comp_(val, que_[father])) { // 默认大于 当前元素比父节点的值大
que_[i] = que_[father];
i = father;
} else {
break;
}
}
// 把val放到i的位置
que_[i] = val;
}
//出堆下沉调整 当前节点与孩子节点比较
void siftDown(int i, int val) {
//i下沉不能超过最后一个有孩子的节点 (size_ - 1 - 1) / 2
while (i <= (size_ - 1 - 1) / 2) {
int child = 2 * i + 1; // 第i个节点的左孩子
if (child + 1 < size_) { // 有右孩子
if (child + 1 < size_ && comp_(que_[child + 1], que_[child])) {
// 如果i节点右孩子大于左孩子, child 记录 右孩子的值
child = child + 1;
}
}
if (comp_(que_[child], val)) {
que_[i] = que_[child];
i = child;
} else {
break; //已经满足堆的性质 提前结束
}
}
que_[i] = val;
}
private:
int* que_; //指向动态扩容的数组
int size_; // 数组元素的个数
int cap_; //数组的总空间大小
Comp comp_; //比较器对象
};
int main() {
// PriorityQueue que; //基于大根堆实现的优先级队列
PriorityQueue que([](int a, int b) {return a < b;}); // 小根堆
srand(time(NULL));
for (int i = 0; i < 10; i++) {
que.push(rand() % 100);
}
while (!que.empty()) {
cout << que.top() << " ";
que.pop();
}
cout << endl;
return 0;
}
到了这里，关于C++基础（三）——STL优先级队列的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
