1、priority_queue的作用
priority_queue即优先级队列,它的使用场景很多,它底层是用大小根堆实现的,可以用log(n)的时间动态地维护数据的有序性。适用于许多场景,比如简化哈夫曼树算法、dijkstra算法等等
priority_queue是不允许随机访问,只能访问队列首部的元素,也只能对首部元素进行出队,下面进行学习它的基本用法
2、priority_queue的定义
头文件
#include<queue>
基本定义方法:
基本定义默认是使用大顶堆的,即队首总是最大的元素
priority_queue<储存的类型> 容器名
如:
priority_queue<int> q;//储存int型数据
priority_queue<double> q;//储存double型数据
priority_queue<string> q;//储存string型数据
priority_queue<结构体名> q;//储存结构体或者类
快速切换大小顶堆定义:
less<储存的数据类型> 即使用大顶堆
greater<储存的数据类型> 即是用小顶堆
priority_queue<储存的类型,vector<储存的类型>,顶堆的类型> 容器名
如:
使用大顶堆的队列:
priority_queue<int,vector<int>,less<int>> q;//储存int型数据
priority_queue<double,vector<double>,less<double>> q;//储存double型数据
priority_queue<string,vector<string>,less<string>> q;//储存string型数据
priority_queue<结构体名,vector<结构体名>,less<结构体名>> q;//储存结构体或者类
使用小顶堆的队列:
priority_queue<int,vector<int>,greater<int>> q;//储存int型数据
priority_queue<double,vector<double>,greater<double>> q;//储存double型数据
priority_queue<string,vector<string>,greater<string>> q;//储存string型数据
priority_queue<结构体名,vector<结构体名>,greater<结构体名>> q;//储存结构体或者类
使用结构体重载运算符定义:
新建一个结构体,通过重载运算符改变顶堆的排序,这里是拓展用法,也是必学用法,因为自己写的结构体是没有比较大小功能的,当然也可以在原本的结构体里面重载运算符
priority_queue<int,vector<int>,cmp> q;//储存int型数据
priority_queue<double,vector<double>,cmp> q;//储存double型数据
priority_queue<string,vector<string>,cmp> q;//储存string型数据
priority_queue<结构体名,vector<结构体名>,cmp> q;//储存结构体或者类
3、priority_queue的成员函数
empty() 如果优先队列为空,则返回真
pop() 删除第一个元素
push() 加入一个元素
size() 返回优先队列中拥有的元素的个数
top() 返回优先队列中有最高优先级的元素
4、priority_queue的基本用法
普通数据类型的使用方法:
示例代码:
#include<iostream>//c++标准头文件,可以使用cout,cin等标准库函数
#include<queue>//使用priority_queue时需要的头文件
using namespace std;//命名空间,防止重名给程序带来各种隐患,使用cin,cout,stack,map,set,vector,queue时都要使用
int main(){
priority_queue<int> q1;//定义一个默认大顶堆的优先级队列q1,即队首元素总是最大值
// priority_queue<int,vector<int>,less<int>> q1; //这样显示定义大顶堆也是可以的
cout<<"定义默认大顶堆q1: priority_queue<int> q1"<<endl;
q1.push(10);//添加一个元素10
q1.push(5);//添加一个元素5
q1.push(7);//添加一个元素7
cout<<"按顺序插入10、5、7这三个数据,目前优先级队列中的元素:10 5 7"<<endl;
cout<<"q1.size()="<<q1.size()<<endl;//查看目前队列中元素个数
cout<<"q1.empty()="<<q1.empty()<<endl;//查看目前队列是否为空,1即为空,0即非空
cout<<"q1.top()="<<q1.top()<<endl;//查看目前队列首部元素
cout<<endl;
q1.pop();
cout<<"q1.pop()后,目前优先级队列中的元素:5 7"<<endl;
cout<<"q1.size()="<<q1.size()<<endl;
cout<<"q1.empty()="<<q1.empty()<<endl;
cout<<"q1.top()="<<q1.top()<<endl;
cout<<endl;
q1.pop();
cout<<"q1.pop()后,目前优先级队列中的元素:5"<<endl;
cout<<"q1.size()="<<q1.size()<<endl;
cout<<"q1.empty()="<<q1.empty()<<endl;
cout<<"q1.top()="<<q1.top()<<endl;
cout<<endl;
q1.pop();
cout<<"q1.pop()后,目前优先级队列是空的"<<endl;
cout<<"q1.size()="<<q1.size()<<endl;
cout<<"q1.empty()="<<q1.empty()<<endl;
cout<<"队列为空时不允许使用q1.top()查看队首元素"<<endl;
cout<<endl<<endl;
priority_queue<int,vector<int>,greater<int>> q2; //定义一个小顶堆的优先级队列q2,即队首元素总是最小值
cout<<"定义小顶堆q2: priority_queue<int,vector<int>,greater<int>> q2"<<endl;
q2.push(10);//添加一个元素10
q2.push(5);//添加一个元素5
q2.push(7);//添加一个元素7
cout<<"按顺序插入10、5、7这三个数据,目前优先级队列中的元素:10 5 7"<<endl;
cout<<"q2.size()="<<q2.size()<<endl;//查看目前队列中元素个数
cout<<"q2.empty()="<<q2.empty()<<endl;//查看目前队列是否为空,1即为空,0即非空
cout<<"q2.top()="<<q2.top()<<endl;//查看目前队列首部元素
cout<<endl;
q2.pop();
cout<<"q2.pop()后,目前优先级队列中的元素:10 7"<<endl;
cout<<"q2.size()="<<q2.size()<<endl;
cout<<"q2.empty()="<<q2.empty()<<endl;
cout<<"q2.top()="<<q2.top()<<endl;
cout<<endl;
q2.pop();
cout<<"q2.pop()后,目前优先级队列中的元素:10"<<endl;
cout<<"q2.size()="<<q2.size()<<endl;
cout<<"q2.empty()="<<q2.empty()<<endl;
cout<<"q2.top()="<<q2.top()<<endl;
cout<<endl;
q2.pop();
cout<<"q2.pop()后,目前优先级队列是空的"<<endl;
cout<<"q2.size()="<<q2.size()<<endl;
cout<<"q2.empty()="<<q2.empty()<<endl;
cout<<"队列为空时不允许使用q1.top()查看队首元素"<<endl;
}
运行结果:
定义默认大顶堆q1: priority_queue<int> q1
按顺序插入10、5、7这三个数据,目前优先级队列中的元素:10 5 7
q1.size()=3
q1.empty()=0
q1.top()=10
q1.pop()后,目前优先级队列中的元素:5 7
q1.size()=2
q1.empty()=0
q1.top()=7
q1.pop()后,目前优先级队列中的元素:5
q1.size()=1
q1.empty()=0
q1.top()=5
q1.pop()后,目前优先级队列是空的
q1.size()=0
q1.empty()=1
队列为空时不允许使用q1.top()查看队首元素
定义小顶堆q2: priority_queue<int,vector<int>,greater<int>> q2
按顺序插入10、5、7这三个数据,目前优先级队列中的元素:10 5 7
q2.size()=3
q2.empty()=0
q2.top()=5
q2.pop()后,目前优先级队列中的元素:10 7
q2.size()=2
q2.empty()=0
q2.top()=7
q2.pop()后,目前优先级队列中的元素:10
q2.size()=1
q2.empty()=0
q2.top()=10
q2.pop()后,目前优先级队列是空的
q2.size()=0
q2.empty()=1
队列为空时不允许使用q1.top()查看队首元素
结构体类型的使用方法
方法一、函数里重载运算符
由于结构体默认是没有比较大小的功能的,所以也就不能直接使用优先级队列,需要重载运行符大于号和小于号,然后使用less<>和greater<>切换大小顶堆
示例代码:
#include<iostream>//c++标准头文件,可以使用cout,cin等标准库函数
#include<queue>//使用priority_queue时需要的头文件
using namespace std;//命名空间,防止重名给程序带来各种隐患,使用cin,cout,stack,map,set,vector,queue时都要使用
struct test{//定义一个结构体test
int val;
test(int v){//构造函数
this->val=v;
}
bool operator > (const test t)const{//重载运算符>
return val>t.val;
}
bool operator < (const test t)const{//重载运算符
return val<t.val;
}
};
int main(){
priority_queue<test,vector<test>,less<test>> q1;//定义一个大顶堆q1
cout<<"定义一个大根堆q1: priority_queue<test,vector<test>,less<test>> q1"<<endl;
q1.push(test(10));//向队列中添加一个test,val的值为10
q1.push(test(5));//向队列中添加一个test,val的值为5
q1.push(test(7));//向队列中添加一个test,val的值为7
cout<<"按顺序添加val的值为10、5、7的test,目前队列的元素:test(10) test(5) test(7)" <<endl;
cout<<"q1.top().val="<<q1.top().val<<endl;
cout<<endl;
q1.pop();
cout<<"q1.pop()后,目前队列的元素:test(5) test(7)"<<endl;
cout<<"q1.top().val="<<q1.top().val<<endl;
cout<<endl;
q1.pop();
cout<<"q1.pop()后,目前队列的元素:test(5)"<<endl;
cout<<"q1.top().val="<<q1.top().val<<endl;
cout<<endl;
q1.pop();
cout<<"q1.pop()后,目前队列是空的"<<endl;
cout<<"目前队列是空的,不能使用q1.top()查询队首元素"<<endl;
cout<<endl<<endl;
priority_queue<test,vector<test>,greater<test>> q2;//定义一个大顶堆q1
cout<<"定义一个小根堆q2: priority_queue<test,vector<test>,greate<test>> q2"<<endl;
q2.push(test(10));//向队列中添加一个test,val的值为10
q2.push(test(5));//向队列中添加一个test,val的值为5
q2.push(test(7));//向队列中添加一个test,val的值为7
cout<<"按顺序添加val的值为10、5、7的test,目前队列的元素:test(10) test(5) test(7)" <<endl;
cout<<"q2.top().val="<<q2.top().val<<endl;
cout<<endl;
q2.pop();
cout<<"q2.pop()后,目前队列的元素:test(10) test(7)"<<endl;
cout<<"q2.top().val="<<q2.top().val<<endl;
cout<<endl;
q2.pop();
cout<<"q2.pop()后,目前队列的元素:test(10)"<<endl;
cout<<"q2.top().val="<<q2.top().val<<endl;
cout<<endl;
q2.pop();
cout<<"q1.pop()后,目前队列是空的"<<endl;
cout<<"目前队列是空的,不能使用q2.top()查询队首元素"<<endl;
}
运行结果:
#include<iostream>//c++标准头文件,可以使用cout,cin等标准库函数
#include<queue>//使用priority_queue时需要的头文件
using namespace std;//命名空间,防止重名给程序带来各种隐患,使用cin,cout,stack,map,set,vector,queue时都要使用
struct test{//定义一个结构体test
int val;
test(int v){//构造函数
this->val=v;
}
bool operator > (const test t)const{//重载运算符>
return val>t.val;
}
bool operator < (const test t)const{//重载运算符
return val<t.val;
}
};
int main(){
priority_queue<test,vector<test>,less<test>> q1;//定义一个大顶堆q1
cout<<"定义一个大根堆q1: priority_queue<test,vector<test>,less<test>> q1"<<endl;
q1.push(test(10));//向队列中添加一个test,val的值为10
q1.push(test(5));//向队列中添加一个test,val的值为5
q1.push(test(7));//向队列中添加一个test,val的值为7
cout<<"按顺序添加val的值为10、5、7的test,目前队列的元素:test(10) test(5) test(7)" <<endl;
cout<<"q1.top().val="<<q1.top().val<<endl;
cout<<endl;
q1.pop();
cout<<"q1.pop()后,目前队列的元素:test(5) test(7)"<<endl;
cout<<"q1.top().val="<<q1.top().val<<endl;
cout<<endl;
q1.pop();
cout<<"q1.pop()后,目前队列的元素:test(5)"<<endl;
cout<<"q1.top().val="<<q1.top().val<<endl;
cout<<endl;
q1.pop();
cout<<"q1.pop()后,目前队列是空的"<<endl;
cout<<"目前队列是空的,不能使用q1.top()查询队首元素"<<endl;
cout<<endl<<endl;
priority_queue<test,vector<test>,greater<test>> q2;//定义一个大顶堆q1
cout<<"定义一个小根堆q2: priority_queue<test,vector<test>,greate<test>> q2"<<endl;
q2.push(test(10));//向队列中添加一个test,val的值为10
q2.push(test(5));//向队列中添加一个test,val的值为5
q2.push(test(7));//向队列中添加一个test,val的值为7
cout<<"按顺序添加val的值为10、5、7的test,目前队列的元素:test(10) test(5) test(7)" <<endl;
cout<<"q2.top().val="<<q2.top().val<<endl;
cout<<endl;
q2.pop();
cout<<"q2.pop()后,目前队列的元素:test(10) test(7)"<<endl;
cout<<"q2.top().val="<<q2.top().val<<endl;
cout<<endl;
q2.pop();
cout<<"q2.pop()后,目前队列的元素:test(10)"<<endl;
cout<<"q2.top().val="<<q2.top().val<<endl;
cout<<endl;
q2.pop();
cout<<"q1.pop()后,目前队列是空的"<<endl;
cout<<"目前队列是空的,不能使用q2.top()查询队首元素"<<endl;
}
方法二、自定义结构体重载括号运算符
很多时候,我们不应该重载结构体的运算符。像数据结构vector,它有它的基本运算方法,我们不应该重载它的运算符。
此时,我们就应该自定义结构体替代less<>和greater<>,通过重载括号符就可以更改比较规则
示例代码:
#include<iostream>//c++标准头文件,可以使用cout,cin等标准库函数
#include<queue>//使用priority_queue时需要的头文件
using namespace std;//命名空间,防止重名给程序带来各种隐患,使用cin,cout,stack,map,set,vector,queue时都要使用
struct test{//定义一个结构体test
int val;
test(int v){//构造函数
this->val=v;
}
// 下面是基本的运算方法,我们不能随意更改它
bool operator > (const test t)const{//重载运算符
return val>t.val;
}
bool operator < (const test t)const{//重载运算符
return val<t.val;
}
};
struct cmp{
bool operator () (const test t1,const test t2)const{//重载括号运算符
return t1.val<t2.val;//小于号是大根堆,大于号是小根堆
}
};
int main(){
priority_queue<test,vector<test>,cmp> q;//自定义一个优先级队列q
cout<<"自定义一个优先级队列q: priority_queue<test,vector<test>,cmp> q"<<endl;
q.push(test(10));//向队列中添加一个test,val的值为10
q.push(test(5));//向队列中添加一个test,val的值为5
q.push(test(7));//向队列中添加一个test,val的值为7
cout<<"q.top().val="<<q.top().val<<endl;
cout<<endl;
q.pop();
cout<<"q.top().val="<<q.top().val<<endl;
cout<<endl;
q.pop();
cout<<"q.top().val="<<q.top().val<<endl;
cout<<endl;
q.pop();
cout<<"目前队列是空的,不能使用q.top()查询队首元素"<<endl;
}
运行结果:
自定义一个优先级队列q: priority_queue<test,vector<test>,cmp> q
q.top().val=10
q.top().val=7
q.top().val=5
目前队列是空的,不能使用q.top()查询队首元素
把括号运算符里的小于号改为大于号就是小顶堆了
自定义一个优先级队列q: priority_queue<test,vector<test>,cmp> q
q.top().val=5
q.top().val=7
q.top().val=10
目前队列是空的,不能使用q.top()查询队首元素
至此,优先级队列的基本用法就学完啦
是不是很简单呢?
刚接触肯定会觉得难,多些做题多些用,熟悉了就容易了,兄弟萌,加油!!!
文章尚有不足,欢迎大牛们指正文章来源:https://www.toymoban.com/news/detail-664084.html
感谢观看,点个赞吧文章来源地址https://www.toymoban.com/news/detail-664084.html
到了这里,关于c++ priority_queue用法 入门必看 超详细的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!