P3378 【模板】堆

说在前面

本题解只是一篇侧重于讲解优先队列做法的题解，请想要详细了解堆的朋友请出门左拐。

如果你觉得你已经掌握了优先队列，可以去这里练练手。

思路

优先队列板子题，这里就简单介绍一下优先队列的 STL 写法（STL 大法好啊）。

定义（以存储 int 类型为例）：

CPP

priority_queue<int> q; //大根堆
priority_queue<int,vector<int>,greater<int> > q; //小根堆
/*区别：大根堆是用来维护堆的最大值的
       而小根堆是用来维护堆的最小值的
      （这里千万不要傻傻分不清楚，当时因为这个我被好基友嘲笑了一整天）
*/

相关函数（常用）

函数用途
q.push(x); 在 q 中插入 x。
q.pop(); 删除 q 中的最值。
q.top(); 返回 q 中的最值。

注意以上操作的时间复杂度都是 $O(log\ n)$ 的。

函数	用途
q.push(x);	在 q 中插入 x。
q.pop();	删除 q 中的最值。
q.top();	返回 q 中的最值。

AC code

CPP

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n,op,x;
priority_queue<int,vector<int>,greater<int> > q;
int main()
{
    ios::sync_with_stdio(0);
    cin>>n;
    while(n--)
    {
        cin>>op;
        if(op==1)
        {
            cin>>x;
            q.push(x);
        }
        else if(op==2)
            cout<<q.top()<<'\n';
        else
            q.pop();
    }
    return 0;
}

仅供参考。

题解：P3378 【模板】堆

文章操作

P3378 【模板】堆

说在前面

思路

AC code

相关推荐

评论

题解：P3378 【模板】堆