c++ std::priority_queue优先队列

首页 > c++ std::priority_queue优先队列

c++ std::priority_queue优先队列

template ,class Compare = less > class priority_queue;

需要头文件 #include

普通的队列是一种先进先出的数据结构，元素在队列尾追加，而从队列头删除。

在优先队列中，元素被赋予优先级。当访问元素时，具有最高优先级的元素最先删除。优先队列具有最高级先出（first in, largest out）的行为特征

priority_queue, greater > q;  // 小顶堆
priority_queue, less > q;     // 大顶堆

priority_queue 优先队列，其底层是用堆来实现的。在优先队列中，队首元素一定是当前队列中优先级最高的那一个。

在优先队列中，没有 front() 函数与 back() 函数，而只能通过 top() 函数来访问队首元素（也可称为堆顶元素），也就是优先级最高的元素。

    //下面两种优先队列的定义是等价的，默认情况下，是降序priority_queue q;priority_queue,less >;//后面有一个空格

1、基本类型优先队列的例子：

#include
#include 
using namespace std;
int main() 
{//对于基础类型 默认是大顶堆priority_queue a; //等同于 priority_queue, less > a;//      这里一定要有空格，不然成了右移运算符    ↓priority_queue, greater > c;  //这样就是小顶堆priority_queue b;for (int i = 0; i < 5; i++) {a.push(i);c.push(i);}while (!a.empty()) {cout << a.top() << ' ';a.pop();} cout << endl;while (!c.empty()) {cout << c.top() << ' ';c.pop();}cout << endl;b.push("abc");b.push("abcd");b.push("cbd");while (!b.empty()) {cout << b.top() << ' ';b.pop();} cout << endl;return 0;
}

运行结果：

4 3 2 1 0
0 1 2 3 4
cbd abcd abc

2、用pair做优先队列元素的例子：

规则：pair的比较，先比较第一个元素，第一个相等比较第二个。

#include 
#include 
#include 
using namespace std;
int main() 
{priority_queue > a;pair b(1, 2);pair c(1, 3);pair d(2, 5);a.push(d);a.push(c);a.push(b);while (!a.empty()) {cout << a.top().first << ' ' << a.top().second << '
';a.pop();}
}

运行结果：

2 5
1 3
1 2

优先队列默认的是从大到小的优先级，但是我们在实际使用的时候，往往需要改变优先级（比如从小到大的排列），这时候就需要改变优先级。

#include 
#include 
using namespace std;//方法1
struct tmp1 //运算符重载<
{int x;tmp1(int a) {x = a;}bool operator<(const tmp1& a) const{return x < a.x; //大顶堆}
};//方法2
struct tmp2 //重写仿函数
{bool operator() (tmp1 a, tmp1 b) {return a.x < b.x; //大顶堆}
};int main() 
{tmp1 a(1);tmp1 b(2);tmp1 c(3);priority_queue d;d.push(b);d.push(c);d.push(a);while (!d.empty()) {cout << d.top().x << '
';d.pop();}cout << endl;priority_queue, tmp2> f;f.push(c);f.push(b);f.push(a);while (!f.empty()) {cout << f.top().x << '
';f.pop();}
}

运行结果：

c++ std::priority_queue优先队列

需要头文件 #include

优先队列默认的是从大到小的优先级，但是我们在实际使用的时候，往往需要改变优先级（比如从小到大的排列），这时候就需要改变优先级。

更多相关：

java 读取excel_Java12POI操作Excel

C++ 生成随机数

基于C++的本征图像分解(Intrinsic Image Decomposition)

剑指offer：面试题39. 数组中出现次数超过一半的数字

剑指offer：面试题33. 二叉搜索树的后序遍历序列

简单C++线程池包装类源码示例

Go 分布式学习利器（11）-- Go语言通过单链表实现队列

C++ STL：stack和queue