优先队列是用堆实现的, 所以优先队列中的 push(),pop() 操作的时间复杂度都是 O(nlogn).
优先队列的初始化需要三个参数, 元素类型, 容器类型, 比较算子.
需要熟悉的优先队列操作:
q.top() 访问堆顶
q.push() 入堆
q.pop() 出堆
不同类型元素的优先级设置
定义堆需要注意最后两个 >> 之间有一个空格
数据结构
- priority_queue <int, vector<int>, Less<int>> q; // 大顶堆 -- 堆顶为大数
- priority_queue <int, vector<int>, greater<int>> q; // 小顶堆 -- 堆顶为小数
例 - 百练 4078: 实现堆结构
AC 代码
- #include<iostream>
- #include<queue>
- #include<vector>
- #include<algorithm>
- using namespace std;
- int main()
- {
- priority_queue <int, vector<int>, greater<int>>q;
- int m, t, x, top;
- cin>> m;
- while (m--)
- {
- cin>> t;
- if (t == 1)
- {
- cin>> x;
- q.push(x);
- }
- if (t == 2)
- {
- top = q.top();
- cout << top << endl;
- q.pop();
- }
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3108732.html