题解 | #【模板】堆#

#include <iostream>
using namespace std;
const int N = 1e5+10;
int n,x;
string s;
int h[N];

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

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

int main()
{
    int size = 0;
	cin>>n;
	while(n--)
	{
		cin>>s;
		if(s == "push")
		{
			cin>>x;
			++size;
			h[size] = x;
			up(size);
		}
		else if(s == "top")
		{
			if(size == 0) cout << "empty" << endl;
			else cout << h[1] << endl;
		}
		else
		{
			if(size == 0) cout << "empty" << endl;
			else
			{
				cout << h[1] << endl;
				h[1] = h[size];
				size--;
				down(1,size);
			}
		}
	}
	return 0;
 }