Zerojudgea091.cpp

#include<stdio.h>
#include<stdlib.h>

int deap[1000005];
int length = 1;

int isMaxHeap( int position )
{
	while( position > 3 )
		position /= 2;
	return (position == 3);
}

int maxPartner( int position )
{
	/* maxPartner = position + 2^([lg(position)] - 1) */
	if( position == 2 )
		return 2;
	int result = position, temp = 1;
	while( position > 3 )
	{
		position /= 2;
		temp *= 2;
	}
	result += temp;
	if( result > length ) return result / 2;
	return result;
}

int minPartner( int position )
{
	/* minPartner = position - 2^([lg(position)] - 1) */
	int result = position, temp = 1;
	while( position > 3 )
	{
		position /= 2;
		temp *= 2;
	}
	result -= temp;
	return result;
}

void maxInsert( int position, int value )
{
	int up = position/2, down = position;
	while( down > 3 && deap[up] < value )
	{
		deap[down] = deap[up];
		down = up;
		up = down/2;
	}
	deap[down] = value;
}

void minInsert( int position, int value )
{
	int up = position/2, down = position;
	while( down > 2 && deap[up] > value )
	{
		deap[down] = deap[up];
		down = up;
		up = down/2;
	}
	deap[down] = value;
}

void insert( int value )
{
	length++;
	if( length == 2 )
	{
		deap[length] = value;
		return;
	}
	else
	{
		int partner;
		if( isMaxHeap(length) )
		{
			partner = minPartner( length );
			if( value < deap[partner] )
			{
				deap[length] = deap[partner];
				minInsert( partner, value );
			}
			else
				maxInsert( length, value );
		}
		else
		{
			partner = maxPartner( length );
			if( value > deap[partner] )
			{
				deap[length] = deap[partner];
				maxInsert( partner, value );
			}
			else
				minInsert( length, value );
		}
	}
}

int maxDelete()
{
	int deap_max = deap[3];
	int deap_last = deap[length--];	
	int i, j;
	for( i = 3, j ; 2*i <= length ; i = j )
	{
		if( 2*i+1 <= length )
			j = ( deap[2*i] > deap[2*i+1] )? 2*i : 2*i+1;
		else
			j = 2*i;
		deap[i] = deap[j];
	}
	int partner = minPartner(i);
	if( 2*partner <= length )
	{
		if( 2*partner+1 <= length && deap[2*partner] < deap[2*partner+1] )
			partner = 2*partner+1;
		else
			partner = 2*partner;
	}
	if( deap_last < deap[partner] )
	{
		deap[i] = deap[partner];
		minInsert( partner, deap_last );
	}
	else
		maxInsert( i, deap_last );
	return deap_max;
}

int minDelete()
{
	int deap_min = deap[2];
	int deap_last = deap[length--];	
	int i, j;
	for( i = 2, j ; 2*i <= length ; i = j )
	{
		if( 2*i+1 <= length )
			j = ( deap[2*i] < deap[2*i+1] )? 2*i : 2*i+1;
		else
			j = 2*i;
		deap[i] = deap[j];
	}
	int partner = maxPartner(i);
	if( deap_last > deap[partner] )
	{
		deap[i] = deap[partner];
		maxInsert( partner, deap_last );
	}
	else
		minInsert( i, deap_last );
	return deap_min;
}

int main()
{
	int control, value;
	while( scanf( "%d", &control ) != EOF )
	{
		switch( control )
		{
			case 1:
				scanf( "%d", &value );
				insert(value);
				break;
			case 2:
				if( length == 2 )
					printf( "%d\n", minDelete() );
				else
					printf( "%d\n", maxDelete() );
				break;
			case 3:
				printf( "%d\n", minDelete() );
				break;
		}
	}
	return 0;
}