admin管理员组文章数量:1623789
优先级队列
当需要获取到最大最小元素值,而又不想用最大最小堆的原生实现,STL提供了更简单的库,就是priority_queue,其时间复杂度也只有
O
(
n
l
o
g
n
)
O(nlogn)
O(nlogn)
priority_queue的本质是一个堆,其相对于queue的不同之处在于:优先队列实现了内部自动排序,可根据自己的需要自定义排序规则,可以自己编写函数或者仿函数用于内部优先级的确定。
头文件为#include
1. 模板声明
priority_queue<Type, Container, Functional>
namespace std {
template < class T ,
class Container = vector<T> ,
class Compare = less <typename Container::value_type> >
class priority_queue ;
}
- Type:数据类型
- Container:保存数据的容器(必须是数组实现的容器,比如vector,deque等,不能使用list,默认为vector。)
- Functional: 元素的比较方式。
元素的优先级取决于设置的排序函数。如果没有设置,缺省的排序法是利用operator< 形成降序排列,也就是从大到小排列的大顶堆,堆首元素为最大的元素。
1.1 基本函数
- top()
- push()
- pop()
2. 代码实例
2.1. 降序排列
#include <iostream>
#include <queue>
using namespace std;
int main(){
priority_queue<int> q;
for( int i= 0; i< 10; ++i ) q.push(i);
while( !q.empty() ){
cout<<q.top()<<endl;
q.pop();
}
return 0;
}
2.2. 返回pair的比较结果,先按照pair的first元素降序,first元素相等时,再按照second元素降序
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
int main(){
priority_queue<pair<int,int> > coll;
pair<int,int> a(3,4);
pair<int,int> b(3,5);
pair<int,int> c(4,3);
coll.push(c);
coll.push(b);
coll.push(a);
while(!coll.empty())
{
cout<<coll.top().first<<"\t"<<coll.top().second<<endl;
coll.pop();
}
return 0;
}
小顶堆:
2.3 如果要用到小顶堆,则一般要把模板的3个参数都带进去。STL里面定义了一个仿函数greater<>,基本类型可以用这个仿函数声明小顶堆。
#include <iostream>
#include <queue>
using namespace std;
int main(){
priority_queue<int, vector<int>, greater<int> > q;
for( int i= 0; i< 10; ++i ) q.push(10-i);
while( !q.empty() ){
cout << q.top() << endl;
q.pop();
}
return 0;
}
2.4 以下代代码返回pair的比较结果,先按照pair的first元素升序,first元素相等时,再按照second元素升序
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
int main(){
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > coll;
pair<int,int> a(3,4);
pair<int,int> b(3,5);
pair<int,int> c(4,3);
coll.push(c);
coll.push(b);
coll.push(a);
while(!coll.empty())
{
cout<<coll.top().first<<"\t"<<coll.top().second<<endl;
coll.pop();
}
return 0;
}
自定义类型
重载operator< 或者重写仿函数
(自定义类型重载operator<后,声明对象时就可以只带一个模板参数)
2.5. 重载operator<:
#include <iostream>
#include <queue>
using namespace std;
struct Node{
int x, y;
Node(int a=0, int b=0):
x(a),y(b){}
};
bool operator<(Node a, Node b){//返回true时,说明a的优先级低于b
//x值较大的Node优先级低(x小的Node排在队前)
//x相等时,y大的优先级低(y小的Node排在队前)
if( a.x== b.x ) return a.y> b.y;
return a.x> b.x;
}
int main(){
priority_queue<Node> q;
for( int i= 0; i< 10; ++i )
q.push( Node( rand(), rand() ) );
while( !q.empty() ){
cout << q.top().x << ' ' << q.top().y << endl;
q.pop();
}
return 0;
}
2.6. 小顶堆:此时不能像基本类型这样声明priority_queue<Node,vector,greater >,原因是greater没有定义,如果想用这种方法定义则可以重载operator >。
#include <iostream>
#include <queue>
using namespace std;
struct Node{
int x, y;
Node( int a= 0, int b= 0 ):
x(a), y(b) {}
};
bool operator>( Node a, Node b ){//返回true,a的优先级大于b
//x大的排在队前部;x相同时,y大的排在队前部
if( a.x== b.x ) return a.y> b.y;
return a.x> b.x;
}
int main(){
priority_queue<Node,vector<Node>,greater<Node> > q;
for( int i= 0; i< 10; ++i )
q.push( Node( rand(), rand() ) );
while( !q.empty() ){
cout << q.top().x << ' ' << q.top().y << endl;
q.pop();
}
return 0;
}
2.7. 重写仿函数的例子
小顶堆:
#include <iostream>
#include <queue>
using namespace std;
struct Node{
int x, y;
Node( int a= 0, int b= 0 ):
x(a), y(b) {}
};
struct cmp{
bool operator() ( Node a, Node b ){//默认是less函数
//返回true时,a的优先级低于b的优先级(a排在b的后面)
// x值大的优先级低,x值大的排在队列后面(升序)
//x相等,y值大的排在队列后面(升序)
if( a.x== b.x ) return a.y> b.y;
return a.x> b.x; }
};
int main(){
priority_queue<Node, vector<Node>, cmp> q;
for( int i= 0; i< 10; ++i )
q.push( Node( rand(), rand() ) );
while( !q.empty() ){
cout << q.top().x << ' ' << q.top().y << endl;
q.pop();
}
return 0;
}
参考:https://wwwblogs/Deribs4/p/5657746.html
本文标签: 优先级队列priorityqueue
版权声明:本文标题:c++ priority_queue优先级队列 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://m.elefans.com/xitong/1728896654a1178498.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论