一, 相关定义
优先队列容器与队列一样, 只能从队尾插入元素, 从队首删除元素. 但是它有一个特性, 就是队列中最大的元素总是位于队首, 所以出队时, 并非按照先进先出的原则进行, 而是将当前队列中最大的元素出队. 这点类似于给队列里的元素进行了由大到小的顺序排序. 元素的比较规则默认按元素值由大到小排序, 可以重载 "<" 操作符来重新定义比较规则.
二, priority_queue
基本操作:
empty() 如果队列为空, 则返回真
pop() 删除对顶元素, 删除第一个元素
push() 加入一个元素
size() 返回优先队列中拥有的元素个数
top() 返回优先队列对顶元素, 返回优先队列中有最高优先级的元素
在默认的优先队列中, 优先级高的先出队. 在默认的 int 型中先出队的为较大的数.
头文件:
#include <queue>
下面看最基本的用法: 从大到小输出
- #include <iostream>
- #include<queue>
- #include<algorithm>
- using namespace std;
- int main(){
- priority_queue<int>que;// 采用默认优先级构造队列
- for(int i=0;i<10;i++)
- {
- int x=rand()%10;
- que.push(x);
- }
- cout<<"采用默认优先关系:"<<endl;
- while(!que.empty())// 从大到小的顺序
- {
- cout<<que.top()<<" ";
- que.pop();
- }
- cout<<endl;
- return 0;
- }
下面是按照从小到大输出 greater 的用法
- #include <iostream>
- #include<queue>
- #include<algorithm>
- #include<vector>
- using namespace std;
- int main()
- {
- priority_queue<int,vector<int>,greater<int>>que;// 采用默认优先级构造队列
- for(int i=0;i<10;i++)
- {
- int x=rand()%10;
- que.push(x);
- }
- cout<<"采用 greater 的优先关系:"<<endl;
- while(!que.empty())// 从小到大输出
- {
- cout<<que.top()<<" ";
- que.pop();
- }
- cout<<endl;
- return 0;
- }
下面看结构体的使用
- #include <iostream>
- #include<queue>
- #include<algorithm>
- #include<vector>
- using namespace std;
- struct number1
- {
- int x;// 下面两种都可以
- /*
- bool operator <(const number1 &a) const
- {
- return x>a.x;
- }*/
- friend bool operator <(number1 a,number1 b)
- {
- return a.x>b.x;//x 小的优先级大
- }
- };
- int main()
- {
- priority_queue<number1>que;//
- for(int i=0;i<10;i++)
- {
- int x=rand()%10;
- number1 n;
- n.x=x;
- que.push(n);
- }
- cout<<"采用结构体定义的优先关系:"<<endl;
- while(!que.empty())// 从小到大
- {
- cout<<que.top().x<<" ";
- que.pop();
- }
- cout<<endl;
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2968993.html