堆(模板)

题目描述

初始小根堆为空，我们需要支持以下3种操作：

操作1： 1 x 表示将x插入到堆中

操作2： 2 输出该小根堆内的最小数

操作3： 3 删除该小根堆内的最小数

Input

第一行包含一个整数N，表示操作的个数

接下来N行，每行包含1个或2个正整数，表示三种操作，格式如下：

操作1： 1 x

操作2： 2

操作3： 3

Output

若干行正整数，每行依次对应一个操作2的结果。

样例输入

5
1 2
1 5
2
3
2

样例输出

2
5

范围提示

对于70%的数据，n<=10^4；
对于100%的数据，n<=10^6。

code:

#include <bits/stdc++.h>
using namespace std;
int a[10001],size;//建立堆与其元素个数 
void push(int x){//添加元素 
	if(size != 0){
		a[++size] = x;
		//调整顺序 
		int t = size;//t指向x的节点 
		while(t > 1 and a[t] < a[t/2]/*如果x比其父节点小*/){
			swap(a[t/2],a[t]);
			t/=2;
		}
	}else{//堆为空 
		a[1] = x;
		size++;
	}
}
void pop(){
	a[1] = a[size--];//把末尾元素移到堆顶 
	int t = 1;//t指向末尾元素 
	while(true){
		if(t*2>size){
			break;
		}else if(a[t*2+1] == 0){
			if(a[t] > a[t*2]){
				swap(a[t],a[t*2]);
				t*=2;
			}else 
				break;
		}else{//左右子节点都存在 
			int y;
			if(a[t*2+1] > a[t*2]) y = t*2;
			else y = t*2+1;
			if(a[y] < a[t]){
				swap(a[y],a[t]);
				t = y;	
			}else
				break;
		}
	}
}
int main(){
	memset(a,0,sizeof(a));
	int n,m;
	scanf("%d",&n);
	for(int i = 1;i<=n;i++){
		scanf("%d",&m);
		if(m == 1){
			int vx;
			scanf("%d",&vx);
			push(vx);
		}else if(m == 2){
			printf("%d\n",a[1]);
		}else{
			pop();
		}
	}
	return 0;
}