优先队列

优先队列(priority_queue)是堆的排列

优先队列的一些性质

首先优先队列是默认是大根堆

一些操作

q.size();//返回q里元素个数
q.empty();//返回q是否为空，空则返回1，否则返回0
q.push(k);//在q的末尾插入k 
q.pop();//删掉q的第一个元素
q.top();//返回q的第一个元素

而优先队列的强大功能就是可以自动排序

https://download.tooc.xlj0.com/uploads/179/%E7%AE%97%E6%B3%95/%E4%BC%98%E5%85%88%E9%98%9F%E5%88%97.png 比如这张图每次插入新的数据都会重新进行排列，如果是大根堆，最上方的节点就是最大值，但是下面的节点并没有确定的顺序。

拿一道默认的优先队列

你有一个菜篮子。

接下来Q次操作，每次操作如下：

1. "1 x"，将一个重量为x的菜放入到菜篮子中。
    
2. "2"，将菜篮子中重量最大的菜丢掉（如果菜篮子为空，则跳过）。
    

问Q次操作后，菜篮子中剩下的菜的总重量。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

constexpr int N = 1e5 + 10;

void solve() {

  int q;

  cin >> q;

  ll sum = 0;

  priority_queue<ll> pq;//默认是大根堆

  while (q--) {

    int c;

    cin >> c;
  
    if (c == 1) {

      ll x;

      cin >> x;

      pq.push(x);

      sum += x;

    } else if (pq.size()) {//判断被删完的情况就没必要加

      sum -= pq.top();

      pq.pop();

    }

  }

  cout << sum << '\n';

}

int main() {

 ios::sync_with_stdio(0);

 cin.tie(0);

 cout.tie(0);

 int a = 1;

 while (a--) {

  solve();

 }

  return 0;

}

小根堆的实现

小根堆就是最上面是最小值

 struct cmp{
   bool operator()(const ll&u,const ll &v)const{
     return u<v;
   }
 };
 priority_queue<T,vector<T>,cmp>pq;

//或者是这样
priority_queue<int,vector<int>,greater<int>> q;