今天的主要是优先级队列的使用
priority_queue学习使用简单的形式
头文件：#include<queue>
优先队列，也就是原来我们学过的堆，按照自己定义的优先级出队时。默认情况下底层是以Vector实现的heap。
函数列表： empty() 如果优先队列为空，则返回真 pop() 删除第一个元素 push() 加入一个元素 size() 返回优先队列中拥有的元素的个数 top() 返回优先队列中有最高优先级的元素
优先队列有入队、出队、判空、大小的操作，并不具备查找功能。
一个我写的简单例子
#include <iostream> #include<queue> using namespace std; int main() { priority_queue<int> q; q.push(2); q.push(5); q.push(13); q.push(32); q.push(153); q.push(342); q.push(355); q.push(342); while(!q.empty()) { cout<<q.top()<<endl; q.pop(); } return 0; }
然后再看一些稍微复杂的
#include<iostream> #include<queue> using namespace std; int main() { int a[10]={3,4,5,2,1,10,8,0,6,7}; //用数组来建立优先级队列 priority_queue<int> q(a,a+10); while(!q.empty()) { cout<<q.top()<<endl; q.pop(); } return 0; }
不用基本类型，改用组合类型
自己创造类型
typedef pair<long,int> Node;
构造函数
priority_queue< Node,vector< Node >,greater< Node > > Q;
这个里面定义了一个制定存放元素(Node),底层实现以vector实现（第二个参数）,优先级为小顶堆(第三个参数)。
前两个参数没什么说的，很好理解，其中第三个参数，默认如下写法：
小顶堆：greater<TYPE>
大顶堆：less<TYPE>
如果想自定义优先级而TYPE不是基本类型，而是复杂类型，例如结构体、类对象，则必须重载其中的operator()，见下面的例子。
#include<iostream> #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;//由顶到下是由大到小 } }; int main() { //初始化 int n; cin>>n; Node *arr=new Node[n]; for(int i=0;i<n;i++) { cin>>arr[i].a>>arr[i].b; } //定义优先队列 ，自定义优先级,注意参数写法 priority_queue<Node,vector<Node>,cmp> q(arr,arr+n); while(!q.empty()) { Node n=q.top(); cout<<n.a<<" "<<n.b<<endl; q.pop(); } return 0; }
题目就不写了，一大堆Getter和Setter，没意思。。。。
下期再见