题解：P3378 【模板】堆

S_Y_B_S · 2025-04-24 21:54:42 · 题解

P3378 【模板】堆

说在前面

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

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

思路

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

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

  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) 的。

  AC code

  #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;
  }

  仅供参考。