P3378 【模板】堆

题目描述

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

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

输入格式

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

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

输出格式

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

输入输出样例

输入 

5
1 2
1 5
2
3
2

输出 

2
5

说明/提示

【数据规模与约定】

• 对于 30% 的数据，保证 n≤15。
• 对于 70% 的数据，保证 n≤10^4。
• 对于 100% 的数据，保证 1≤n≤10^6，1≤x<23^1，op∈{1,2,3}。

AC代码： 

#include<iostream>
#include<algorithm>

using namespace std;

const int N = 1e6+10;
int h[N],size;

void down(int u)
{
	int t = u;
	if(u*2 <= size && h[u*2] < h[t]) t = u * 2;
	if(u*2+1 <= size && h[u*2+1] < h[t]) t = u*2+1;
	if(t != u)
	{
		swap(h[t],h[u]);
		down(t);
	}
}

void up(int u)
{
	while(u/2 && h[u/2] > h[u])
	{
		swap(h[u],h[u/2]);
		u = u/2;	
	} 
}

int main()
{
	int n;
	cin >> n;
	while(n--)
	{
		int op;
		cin >> op;
		if(op == 1)
		{
			int x;
			cin >> x;
			size++;
			h[size] = x;
			up(size);	
		}
		else if(op == 2)
		{
			printf("%d\n",h[1]);
		}	
		else
		{
			h[1] = h[size];
			size--;
			down(1);
		}
	}
	return 0;
}