一, 相关定义
优先队列容器与队列一样, 只能从队尾插入元素, 从队首删除元素. 但是它有一个特性, 就是队列中最大的元素总是位于队首, 所以出队时, 并非按照先进先出的原则进行, 而是将当前队列中最大的元素出队. 这点类似于给队列里的元素进行了由大到小的顺序排序. 元素的比较规则默认按元素值由大到小排序, 可以重载 "<" 操作符来重新定义比较规则.
优先级队列可以用向量 (vector) 或双向队列 (deque) 来实现(注意 list container 不能用来实现 queue, 因为 list 的迭代器不是任意存取 iterator, 而 pop 中用到堆排序时是要求 randomaccess iterator 的!):
- priority_queue<vector<int>, Less<int>> pq1; // 使用递增 Less<int > 函数对象排序
- priority_queue<deque<int>, greater<int>> pq2; // 使用递减 greater<int > 函数对象排序
其成员函数有 "判空(empty)" ,"尺寸(Size)" ,"栈顶元素(top)" ,"压栈(push)" ,"弹栈(pop)" 等.
二, priority_queue
基本操作:
empty() 如果队列为空, 则返回真
pop() 删除对顶元素, 删除第一个元素
push() 加入一个元素
size() 返回优先队列中拥有的元素个数
top() 返回优先队列对顶元素, 返回优先队列中有最高优先级的元素
在默认的优先队列中, 优先级高的先出队. 在默认的 int 型中先出队的为较大的数.
头文件:
#include <queue>
声明方式:
1, 普通方法:
- priority_queue<int> q; // 通过操作, 按照元素从大到小的顺序出队
- priority_queue<int,vector<int>, greater<int>> q; // 通过操作, 按照元素从小到大的顺序出队
2, 自定义优先级:
- struct cmp {
- operator bool ()(int x, int y)
- {
- return x > y; // x 小的优先级高 // 也可以写成其他方式, 如: return p[x] > p[y]; 表示 p[i]小的优先级高
- }
- };
- priority_queue<int, vector<int>, cmp> q; // 定义方法
- // 其中, 第二个参数为容器类型. 第三个参数为比较函数.
3, 结构体声明方式:
- struct node {
- int x, y;
- friend bool operator < (node a, node b)
- {
- return a.x > b.x; // 结构体中, x 小的优先级高
- }
- };
- priority_queue<node>q; // 定义方法
- // 在该结构中, y 为值, x 为优先级.
- // 通过自定义 operator < 操作符来比较元素中的优先级.
- // 在重载 "<" 时, 最好不要重载 ">", 可能会发生编译错误
三, 代码实现
优先队列, 其构造及具体实现我们可以先不用深究, 我们现在只需要了解其特性, 及在做题中的用法.
以一个例子来解释吧(呃, 写完才发现, 这个代码包函了几乎所有我们要用到的用法, 仔细看看吧):
- /* 优先队列的基本使用 2017/8/1 xzxl*/
- #include<stdio.h>
- #include<functional>
- #include<queue>
- #include<vector>
- using namespace std;
- // 定义结构, 使用运算符重载, 自定义优先级 1
- struct cmp1{
- bool operator ()(int &a,int &b){
- return a>b;// 最小值优先
- }
- };
- struct cmp2{
- bool operator ()(int &a,int &b){
- return a<b;// 最大值优先
- }
- };
- // 定义结构, 使用运算符重载, 自定义优先级 2
- struct number1{
- int x;
- bool operator <(const number1 &a) const {
- return x>a.x;// 最小值优先
- }
- };
- struct number2{
- int x;
- bool operator <(const number2 &a) const {
- return x<a.x;// 最大值优先
- }
- };
- int a[]={14,10,56,7,83,22,36,91,3,47,72,0};
- number1 num1[]={14,10,56,7,83,22,36,91,3,47,72,0};
- number2 num2[]={14,10,56,7,83,22,36,91,3,47,72,0};
- int main()
- { priority_queue<int>que;// 采用默认优先级构造队列
- priority_queue<int,vector<int>,cmp1>que1;// 最小值优先
- priority_queue<int,vector<int>,cmp2>que2;// 最大值优先
- priority_queue<int,vector<int>,greater<int>>que3;// 注意 ">>" 会被认为错误,
- // 这是右移运算符, 所以这里用空格号隔开
- priority_queue<int,vector<int>,Less<int>>que4;//// 最大值优先
- priority_queue<number1>que5;
- priority_queue<number2>que6;
- int i;
- for(i=0;a[i];i++){
- que.push(a[i]);
- que1.push(a[i]);
- que2.push(a[i]);
- que3.push(a[i]);
- que4.push(a[i]);
- }
- for(i=0;num1[i].x;i++)
- que5.push(num1[i]);
- for(i=0;num2[i].x;i++)
- que6.push(num2[i]);
- printf("采用默认优先关系:\n(priority_queue<int>que;)\n");
- printf("Queue 0:\n");
- while(!que.empty()){
- printf("=",que.top());
- que.pop();
- }
- puts("");
- puts("");
- printf("采用结构体自定义优先级方式一:\n(priority_queue<int,vector<int>,cmp>que;)\n");
- printf("Queue 1:\n");
- while(!que1.empty()){
- printf("=",que1.top());
- que1.pop();
- }
- puts("");
- printf("Queue 2:\n");
- while(!que2.empty()){
- printf("=",que2.top());
- que2.pop();
- }
- puts("");
- puts("");
- printf("采用头文件 \"functional\"内定义优先级:\n(priority_queue<int,vector<int>,greater<int>/less<int>>que;)\n");
- printf("Queue 3:\n");
- while(!que3.empty()){
- printf("=",que3.top());
- que3.pop();
- }
- puts("");
- printf("Queue 4:\n");
- while(!que4.empty()){
- printf("=",que4.top());
- que4.pop();
- }
- puts("");
- puts("");
- printf("采用结构体自定义优先级方式二:\n(priority_queue<number>que)\n");
- printf("Queue 5:\n");
- while(!que5.empty()){
- printf("=",que5.top());
- que5.pop();
- }
- puts("");
- printf("Queue 6:\n");
- while(!que6.empty()){
- printf("=",que6.top());
- que6.pop();
- }
- puts("");
- return 0;
- }
- /*
- 运行结果 :
- 采用默认优先关系:
- (priority_queue<int>que;)
- Queue 0:
- 83 72 56 47 36 22 14 10 7 3
- 采用结构体自定义优先级方式一:
- (priority_queue<int,vector<int>,cmp>que;)
- Queue 1:
- 7 10 14 22 36 47 56 72 83 91
- Queue 2:
- 83 72 56 47 36 22 14 10 7 3
- 采用头文件 "functional" 内定义优先级:
- (priority_queue<int,vector<int>,greater<int>/Less<int>>que;)
- Queue 3:
- 7 10 14 22 36 47 56 72 83 91
- Queue 4:
- 83 72 56 47 36 22 14 10 7 3
- 采用结构体自定义优先级方式二:
- (priority_queue<number>que)
- Queue 5:
- 7 10 14 22 36 47 56 72 83 91
- Queue 6:
- 83 72 56 47 36 22 14 10 7 3
- */
来源: http://www.bubuko.com/infodetail-3020944.html