关于priority_queue

时间：2025-04-04 08:20:24

priority_queue允许用户为队列中元素设置优先级，放置元素的时候不是直接放到队尾，而是放置到比它优先级低的元素前面，标准库默认使用<操作符来确定优先级关系。

priority_queue模板类有三个模板参数：元素类型，容器类型，比较算子。其中后两个可以省略，默认容器为vector，默认算子为less，即如果x<y判断为真，则y排到x前面，y先出队。

定义priority_queue对象的示例代码如下：

priority_queue<int> q1;

priority_queue<pair<int,int>> q2;

priority_queue<int,vector<int>,greater<int>> q3;//定义优先级小的先出队

priority_queue与queue的基本操作均相同，在使用()时返回最高优先级的元素，该操作只适用于优先级队列。

如果要自己定义比较算子，可以有多种方法，最常见的就是重载比较运算符，注意重载操作返回的结果是bool类型，并且此处的比较操作与map等其他处不同，在map中以<作为比较操作，则值小的排在前面，而优先级队列中以<作为比较操作，来确定优先级关系，此处表明优先级关系为按值从小到大排列，值大的优先级高，而优先级高的放在队列前面，反之以>操作符确定优先级关系时，表明优先级是按值从大到小排列，值小的优先级高，优先级高的放在队列前面。

下面代码创建一个简单的优先级队列，默认按照less确定优先级，即<操作符，先使用top返回最高优先级元素，然后使用pop删除队首元素，然后再返回最高优先级元素top，可以看出top由9变为5，表明最高优先级的排在队首：

#include <iostream>
#include <queue>
using namespace std;
int main ()
{
	priority_queue<int> q;
	(1);
	(5);
	(3);
	(9);
	(2);
	cout<<()<<endl;
	();
	cout<<()<<endl;
	system("pause");
	return 0;
}
结果如下：



下面这个例子是在priority_queue中插入(x,y,z)为一个元素的值，并且定义比较其中的z值来确定优先级顺序，z值大的排在队列前面：

#include<iostream>  
#include<queue>  
#include<>  
using namespace std;  
class T  
{  
public:  
    int x,y,z;  
    T(int a,int b,int c):x(a),y(b),z(c)  
    {  
    }  
};  
bool operator<(const T&t1,const T&t2)  
{  
    return <;  
}  
int main(void)  
{  
    priority_queue<T>q;  
    (T(4,4,3));  
    (T(2,2,5));  
    (T(1,5,4));  
    (T(3,3,6));  
    while(!())  
    {  
        T t=();  
        ();  
        cout<<<<" "<<<<" "<<<<endl;  
    }  
    system("Pause");  
    return 1;  
}

本文内容参考自 STL系列之五 priority_queue 优先级队列 以及  c++queue容器介绍

相关文章