[模板] 堆 heap

//进阶指南版

struct HEAP
{
	ll heap[MAXN], len;
	
	HEAP()
	{
		memset(heap, 0, sizeof(ll) * MAXN);
		len = 0;
	}

	void up(int now)
	{
		while(now > 1)
		{
			if(heap[now] < heap[now / 2])
				swap(heap[now], heap[now / 2]), now /= 2;
			else
				break;
		}
	}

	ll top()
	{
		return heap[1];
	}

	void push(ll x)
	{
		heap[++len] = x;
		up(len);
	}

	void down(int now)
	{
		int po = now * 2;

		while(po <= len)
		{
			if(po < len && heap[po] > heap[po + 1])
				++po;

			if(heap[now] > heap[po])
				swap(heap[now], heap[po]), now = po, po *= 2;

			else
				break;
		}
	}

	void pop()
	{
		heap[1] = heap[len--];
		down(1);
	}

	void remove(int now)
	{
		heap[now] = heap[len--];
		up(now), down(now);
	}
};

//挑战程序设计版 

//Zeolim - An AC a day keeps the bug away
// 
//#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MAXN = 1e6 + 10;

ll heap[MAXN] = {0}, size = 1;

void push(ll x)
{
    ll i = size++;

    while(i > 1)
    {
        ll p = i / 2;

        if(heap[p] <= x)
            break;
        heap[i] = heap[p];

        i = p;
    }

    heap[i] = x;
}

void pop()
{
    ll x = heap[--size];

    ll i = 1;

    while(i * 2 < size)
    {
        ll a = i * 2, b = i * 2 + 1;

        if(b < size && heap[b] < heap[a])
            a = b;

        if(heap[a] >= x)
            break;

        heap[i] = heap[a];

        i = a;
    }
    heap[i] = x;
}

ll top()
{
    return heap[1];
}

int main()
{
    //ios::sync_with_stdio(false);
    //cin.tie(0)        cout.tie(0);
    //freopen("D:in.txt","r",stdin);
    //freopen("D:out.txt","w",stdout); 
    
    int n;

    cin>>n;

    while(n--)
    {
        int a, b;
        cin>>a;
        
        if(a == 1)
        {
            cin>>b;
            push(b);
        }
        else if(a == 2)
        {
            cout<<top()<<endl;
        }
        else
            pop();
    }

    return 0;
}