【模板】堆
题目描述
给定一个数列,初始为空,请支持下面三种操作:
- 给定一个整数 x x x,请将 x x x 加入到数列中。
- 输出数列中最小的数。
- 删除数列中最小的数(如果有多个数最小,只删除 1 1 1 个)。
输入格式
第一行是一个整数,表示操作的次数 n n n。
接下来 n n n 行,每行表示一次操作。每行首先有一个整数 o p op op 表示操作类型。
- 若 o p = 1 op = 1 op=1,则后面有一个整数 x x x,表示要将 x x x 加入数列。
- 若 o p = 2 op = 2 op=2,则表示要求输出数列中的最小数。
- 若 o p = 3 op = 3 op=3,则表示删除数列中的最小数。如果有多个数最小,只删除 1 1 1 个。
输出格式
对于每个操作 2 2 2,输出一行一个整数表示答案。
样例 #1
样例输入 #1
5
1 2
1 5
2
3
2
样例输出 #1
2
5
提示
【数据规模与约定】
- 对于 30 % 30\% 30% 的数据,保证 n ≤ 15 n \leq 15 n≤15。
- 对于 70 % 70\% 70% 的数据,保证 n ≤ 1 0 4 n \leq 10^4 n≤104。
- 对于 100 % 100\% 100% 的数据,保证 1 ≤ n ≤ 1 0 6 1 \leq n \leq 10^6 1≤n≤106, 1 ≤ x < 2 31 1 \leq x \lt 2^{31} 1≤x<231, o p ∈ { 1 , 2 , 3 } op \in \{1, 2, 3\} op∈{ 1,2,3}。
思路
定义一个最小值优先的优先队列,它是一个最小堆,即队列顶部始终是队列中最小的元素。然后,程序读取用户输入的一个整数n,表示接下来将进行n次操作。
每次操作开始时,程序会读取一个操作码op。如果操作码是1,那么程序会再读取一个整数t,然后将t插入到最小堆中。如果操作码是2,程序会输出当前最小堆的顶部元素,也就是最小的元素。如果操作码是3,程序会删除最小堆的顶部元素。
AC代码
#include <iostream>
#include <queue>
#define AUTHOR "HEX9CF"
using namespace std;
int n;
priority_queue<int, vector<int>, greater<int>> hmin;
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
int op;
int t;
cin >> op;
switch (op) {
case 1:
cin >> t;
hmin.push(t);
break;
case 2:
cout << hmin.top() << endl;
break;
case 3:
hmin.pop();
break;
}
}
return 0;
}