题目链接：【模板】堆

【模板】堆

题目描述

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

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

输入格式

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

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

输出格式

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

样例 #1

样例输入 #1

51 21 5232

样例输出 #1

25

提示

【数据规模与约定】

• 对于 $30\mathrm{\%}$ 的数据，保证 $n\le 15$。
• 对于 $70\mathrm{\%}$ 的数据，保证 $n\le {10}^4$。
• 对于 $100\mathrm{\%}$ 的数据，保证 $1\le n\le {10}^6$，$1\le x<2^{31}$，$op\in \{1,2,3\}$。

这道题考察的是小顶堆的使用

方法一：暴力求解(代码这里就不写了)

方法二：手写堆

#include<bits/stdc++.h>using namespace std;long long n,heap[10000000],t=0;void sup(int i){	int flag=0;	if(i==1)return ;	while(i!=1&&flag==0){		if(heap[i]<heap[i/2])			swap(heap[i],heap[i/2]);		else			flag=1;		i/=2;	}}void sdown(int i){	int l,f=0;	while(i*2<=t&&f==0){		if(heap[i]>heap[i*2])			l=i*2;		else			l=i;		if(i*2+1<=t){			if(heap[l]>heap[i*2+1])				l=2*i+1;		} 		if(l!=i){			swap(heap[l],heap[i]);			i=l;		}else			f=1;	}}void del(int i){	heap[i]=heap[t];	t--;	sdown(i);}int main(){	cin>>n;	int op;	for(int i=1;i<=n;i++){		cin>>op;		if(op==1){			cin>>heap[++t];			sup(t);		}		if(op==2){			cout<<heap[1]<<endl;		}		if(op==3){			del(1);		}	}	return 0;}

方法三：STL优先队列

#include<bits/stdc++.h>using namespace std;int n,x;int main(){	priority_queue <int,vector<int>,greater<int> > q;	cin>>n;	int op;	for(int i=1;i<=n;i++){		cin>>op;		if(op==1){			cin>>x;			q.push(x);		}		if(op==2){			cout<<q.top()<<endl;		}		if(op==3){			q.pop();		}	}	return 0;}