手写堆求调,玄关

P3378

记录详情

#include<bits/stdc++.h>
using namespace std;
long long x,n;
long long qn[1145140],cnt;
char op;
long long a,res,j;

int main()
{
	cin>>n;
	while(n--)
	{
		cin>>op;
		if(op=='1')
		{
			cnt++;
			cin>>qn[cnt];
			j=cnt;
			while(1)
			{
				if(qn[j]<qn[j>>1])
				{
					swap(qn[j],qn[j>>1]);
					j=j>>1;
				}
				else
				 break;
			}
		}
		else if(op=='2')
			cout<<qn[1]<<endl;
		else if(op=='3')
		{
			swap(qn[1],qn[cnt]);
			cnt--;
			res=1;
			if(qn[2]<=qn[3])
			  j=2;
			else
			  j=3;
			while(1)
			{
			  if(qn[res]<=qn[j]||j>cnt)
				    break;
				else if(qn[res]>qn[j])
				{
					swap(qn[res],qn[j]);
					res=j;
					if(qn[j<<1]<=qn[j<<1|1]&&qn[j<<1]<qn[j])
					  j=(j<<1);
					else if(qn[j<<1|1]<qn[j<<1|1]&&qn[j<<1|1]<qn[j])
					  j=(j<<1|1);  
							
				}
				 	  
			}	  
		}
		
		
		
	}
	
	
	
	return 0;
}