C++优先队列的使用 - 好文

转载自https://blog.csdn.net/u012804490/article/details/26241523
<https://blog.csdn.net/u012804490/article/details/26241523>
优先队列(priority queue)亦即数据结构中的堆
，是计算机科学中一类特殊的数据结构的统称。在队列中，调度程序反复提取队列中第一个作业并运行，因而实际情况中某些时间较短的任务将等待长时间才能结束，或某些不短小，但具有重要性的作业，同样应当具有优先权。优先队列即为解决此类问题设计的一种数据结构。优先队列(堆)通常是一个可以被看做一棵树的数组对象。

优先队列中的常用函数：

empty() 如果优先队列为空，返回真

pop() 删除第一个元素

push(x) 添加一个元素x

size() 返回优先队列中拥有的元素的个数

top() 返回优先队列中有最高优先级的元素

例如：
#include<iostream> #include<cstdio> #include<queue> using namespace std; int
main() {int i; priority_queue<int> q; //定义优先队列 // 向队列中添加元素 q.push(4); q.push(1
); q.push(3); q.push(5); q.push(6); q.push(2); int len=q.size(); // 统计优先队列中元素的个数
for(i=0;i<len;i++) { // top()返回优先级最高的元素 // 在优先队列中，默认为大根堆，即默认元素大的优先级高 printf("%d
",q.top()); q.pop(); // 删除第一个元素，也即优先级最高的元素 } printf("\n"); if(q.empty()) //
此时该优先队列中元素已删除完 printf("该优先队列为空\n"); return 0; }
输出结果为：
6 5 4 3 2 1

该优先队列为空
如果我们希望在优先队列中的较小的元素优先出队，该怎么做呢？

So easy！

我们只需将priority_queue q;改为priority_queue
#include<iostream> #include<cstdio> #include<queue> using namespace std; int
main() {int i; priority_queue<int,vector<int>,greater<int> > q; // 向队列中添加元素
q.push(4); q.push(1); q.push(3); q.push(5); q.push(6); q.push(2); int
len=q.size();// 统计优先队列中元素的个数 for(i=0;i<len;i++) { // top()返回优先级最高的元素 //
在优先队列中，默认为大根堆，即默认元素大的优先级高 printf("%d ",q.top()); q.pop(); // 删除第一个元素，也即优先级最高的元素
}printf("\n"); if(q.empty()) // 此时该优先队列中元素已删除完 printf("该优先队列为空\n"); return 0; }
运行结果：
1 2 3 4 5 6

该优先队列为空

greater变为less的这里不再验证，请有兴趣的童鞋自己验证！

拓展：
优先队列还可以将一个普通数组中的元素转化为优先队列的初始值！

代码如下：
#include<iostream> #include<cstdio> #include<queue> using namespace std; int
main() {int a[6]={3,2,1,4,6,5}; priority_queue<int> q(a,a+6); //普通数组元素作为优先队列的元素
while(!q.empty()) { printf("%d ",q.top()); q.pop(); } printf("\n"); return 0; }
运行结果：
6 5 4 3 2 1

代码2：
#include<iostream> #include<cstdio> #include<queue> using namespace std; int
main() {int a[6]={3,2,1,4,6,5}; priority_queue<int> q(&a[2],a+6); // &a[2]表示以a[2
]的地址为开始地址，a+6表示数组的结束地址 while(!q.empty()) { printf("%d ",q.top()); q.pop(); }
printf("\n"); return 0; }
运行结果：
6 5 4 1

* 如果想自定义优先级并且数据类型不是基本数据类型，而是复杂数据类型，则必须重载其中的operator(); #include<iostream>
#include<cstdio> #include<queue> using namespace std; typedef struct { int a;
int b; }Node; // 自定义优先级 struct cmp { bool operator()(const Node &t1,const Node
&t2) {return t1.b<t2.b; // 相当于less，数据元素值大的优先级高 } }; int main() { int i,n; scanf
("%d",&n); Node *num=new Node[n]; for(i=0;i<n;i++) { scanf("%d%d"
,&num[i].a,&num[i].b); } priority_queue<Node,vector<Node>,cmp> q(num,num+n);
//初始化优先队列 while(!q.empty()) { printf("%d ",q.top().b); q.pop(); } printf("\n");
return 0; }
输入：
3

3 8

5 6

4 7

输出结果：

8 7 6

热门工具换一换