【模板】堆
题目描述
给定一个数列,初始为空,请支持下面三种操作:
- 给定一个整数 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}。
/*****************************************
备注:luoguribao
******************************************/
#include<queue>
#include<math.h>
#include<stack>
#include<stdio.h>
#include<iostream>
#include<vector>
#include<iomanip>
#include<map>
#include<string.h>
#include<algorithm>
using namespace std;
typedef long long LL;
const int MAXN = 1e6 + 10;
const int MR = 10 + 5;
const int INF = 0x3f3f3f3f;
const int MOD = 998244353;
int size, heap[MAXN];
void push_up(int &i,int val){
while(i > 1 && val < heap[i / 2]){
heap[i] = heap[i / 2];
i /= 2;
}
}
void push_down(int &i,int val){
int ch = i * 2;
while(ch <= size){
if(ch < size && heap[ch + 1] < heap[ch])ch++;
if(val <= heap[ch])break;
heap[i] = heap[ch];
i = ch;
ch += ch;
}
}
void insert(int val){
int i = ++size;
push_up(i, val);
heap[i] = val;
}
void delete_min(){
int i = 1, val = heap[size--];
push_down(i, val);
heap[i] = val;
}
signed main()
{
int n;
cin >> n;
for(int i = 1;i <= n; i++){
int opt, x;
cin >> opt;
if(opt == 1){
cin >> x;
insert(x);
}
if(opt == 2){
cout << heap[1] << endl;
}
if(opt == 3){
delete_min();
}
}
return 0;
}