堆排序模板

#include<bits/stdc++.h>
using namespace std;
#define ioio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define debug(x) cout<<#x<<":"<<x<<endl;
#define endl "\n"
#define P pair
#define P1 first
#define P2 second
#define u_map unordered_map
#define p_queue priority_queue
typedef long long ll;
const double eps = 1e-6;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const int N = 1e6 + 7;
int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};
/*-------------------------------------*/

int n;
int h[N],ind;

void down(int x){
	int t=x;
	if(2*x<=ind&&h[2*x]>h[t])t=2*x;
	if(2*x+1<=ind&&h[2*x+1]>h[t])t=2*x+1;
	if(t!=x){
		swap(h[x],h[t]);
		down(t);
	}
}
void up(int x){
	int t=x;
	if(x/2>=1&&h[x/2]<h[x])t=x/2;
	if(t!=x){
		swap(h[x],h[t]);
		up(t);
	}
}
void pop(){
	if(ind<1){
		cout<<"Empty"<<endl;
		return ;
	}
	else cout<<h[1]<<endl;
	h[1]=h[ind];
	ind--;
	down(1);
}
void push(int x){
	h[++ind]=x;
	up(ind);
}
int main(){
	ioio
	cin>>n;
	string op;
	int x;
	while(n--){
		cin>>op;
		if(op=="pop")pop();
		else {
			cin>>x;
			push(x);
		}
	}
	return 0;
}