【模板】堆

题目描述

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

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

输入格式

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

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

输出格式

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

样例 #1

样例输入 #1

5
1 2
1 5
2
3
2

样例输出 #1

2
5

提示

【数据规模与约定】

• 对于 \(30\%\) 的数据，保证 \(n \leq 15\)。
• 对于 \(70\%\) 的数据，保证 \(n \leq 10^4\)。
• 对于 \(100\%\) 的数据，保证 \(1 \leq n \leq 10^6\)，\(1 \leq x \lt 2^{31}\)，\(op \in \{1, 2, 3\}\)。

题解

一道模板题罢了

#include <iostream>
#include <queue>
using namespace std;

int main()
{

	priority_queue<int, vector<int>, greater<int>> q; // 使用最小堆

	int _;cin >> _;

	while (_--) {

		int op; cin >> op;

		switch (op)
		{
			// 输入 
		case 1:
			int x; cin >> x;
			q.push(x);
			break;

			// 输出
		case 2:
			cout << q.top() << endl;
			break;
			// 删除
		case 3:
			if (!q.empty())q.pop();
			break;
		}
	}
	return 0;
}