priority_queue
优先队列，也叫"堆"，仅维护最大/最小元素，可以在较小的时间复杂度内获取某个元素集合的最大或最小值
优先队列常用于贪心、优化dp、构造、dijkstra、prim等问题或算法中，应用非常广泛
声明
//默认为大根堆
priority_queue<int> pq;
//改为小根堆
priority_queue<int,vector<int>,greater<int>> pq;
//比较复杂的结构，比如说pair和结构体等时使用自定义函数
//自定义比较函数常用方法
//方法一：全局函数，传入函数指针用decltype转换
bool cmp(const int &u,const int &v){
return u<u;
}
priority_queue<int, vector<int>,decltype(&cmp)> pq(cmp);
//方法二：匿名函数用cmp变量存储，传入变量
auto cmp = [](const int &u, const int &v){
return u<v;//大根堆
};
priority_queue<int,vector<int>,decltype(cmp)> pq(cmp);
//方法三：struct重载()运算符
struct cmp{
bool operator()(const int &u, const int &v){
return u<v;//大根堆
}
}
priority_queue<int,vector<int>,cmp> pq;
常规操作
//取出堆顶元素，时间复杂度为O(1)
cout << pq.top() << '\n';
//入堆，O(logn)，n为堆内元素个数
pq.push(x);
//出堆，O(logn)，n为堆内元素个数
pq.pop(); //注意保证pq非空
//获取堆内元素个数，即堆的大小
cout << pq.size() << '\n';
优先队列为树形结构，不支持遍历（除非逐个出堆）
小e吃松果
小e吃松果 | 星码StarryCoding 算法竞赛新手村
代码
#include<bits/stdc++.h> using namespace std; using ll = long long; int main(){ int n;cin>>n; priority_queue<ll,vector<ll>,greater<ll>> pq; for(int i=1;i<=n;i++){ ll x;cin>>x; pq.push(x); } ll ans=0; while(pq.size()>1){ ll x=pq.top();pq.pop(); ll y=pq.top();pq.pop(); ans+=x+y; pq.push(x+y); } cout << ans <<endl; return 0; }
)
