|
#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; |
|
} |
