$$【模板】堆$$

题目链接：$\mathrm{l}\mathrm{u}\mathrm{o}\mathrm{g}\mathrm{u}\mathrm{P}3378$

题目

给定一个数列，初始为空，请支持下面三种操作：

1. 给定一个整数 $x$ ，请将 $x$ 加入到数列中。
2. 输出数列中最小的数。
3. 删除数列中最小的数（如果有多个数最小，只删除 $1$ 个）。

输入

第一行是一个整数，表示操作的次数 $n$ 。
接下来 $n$ 行，每行表示一次操作。每行首先有一个整数 $op$ 表示操作类型。

1. 若 $op=1$ ，则后面有一个整数 $x$ ，表示要将 $x$ 加入数列。
2. 若 $op=2$ ，则表示要求输出数列中的最小数。
3. 若 $op=3$ ，则表示删除数列中的最小数。如果有多个数最小，只删除 $1$ 个。

输出

对于每个操作 $2$ ，输出一行一个整数表示答案。

样例输入

5
1 2
1 5
2
3
2

样例输出

2
5

数据范围

• 对于 $30\%$ 的数据，保证 $n\le 15$。
• 对于 $70\%$ 的数据，保证 $n\le 10^4$。
• 对于 $100\%$ 的数据，保证 $1\le n\le 10^6$，$1\le x<2^{31}$， o p ∈ { 1 , 2 , 3 } op \in \{1, 2, 3\} op∈{1,2,3}。

思路

一道模板题。

堆分为大根堆和小根堆，这里就直说小根堆的，大根堆同理。
其实就是维护一棵树，让根节点小于它的两个儿子。

手打其实非常麻烦，C++ 又自带函数，就很香。
priority_queue <int, vector<int>, greater<int> > q;
priority_queue <int> q;（默认是大根堆）
如果要大根堆，就是这个：（把 greater改成less）
priority_queue <int, vector<int>, less<int> > q;

然后如果你还可以用 pair，然后优先比较的则是 first 的（就是第一个）
当然你也可以用重载运算符之类的玩意儿，来让一个点包含更多的内容，比较更加的复杂。

所以我就只用了函数的，手打的之前打过，可以点开链接看看：
题目：旅行（做法为 k 短路加堆优化）

链接：https://blog.csdn.net/weixin_43346722/article/details/107953531

我这里就讲一讲堆的思路吧，以小根堆为例子：

1. 插入操作：就是把一个点放在最下面，然后就不断上浮。
   （上浮就是如果它上面的比他大就交换位置，直到不行）
2. 删除操作：就是把根扔掉，然后把最后一个点拎到根，让他下沉。
   或者说把根的值赋值为最后一个点的，然后点的个数减少，然后再不断下沉。
   （下沉就是如果它的两个儿子有比它小的就把它换上来，如果两个都比他大就换更小的上来）
3. 查询操作：就是根。

代码

#include<queue>
#include<cstdio>

using namespace std;

int n, x, y;
priority_queue <int, vector<int>, greater<int> > q;

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &x);
		if (x == 1) {
			scanf("%d", &y);
			q.push(y);
		}
		else if (x == 2) {
			printf("%d\n", q.top());
		}
		else if (x == 3) {
			q.pop();
		}
	}
	
	return 0;
}