Cod sursa(job #789122)
//
// main.cpp
// Heapuri
//
// Created by Ioana Teoc on 9/16/12.
// Copyright (c) 2012 Ioana Teoc. All rights reserved.
//
#include <iostream>
#include <stdio.h>
#define MAXN 200010
using namespace std;
int Heap[MAXN], Pos[MAXN], A[MAXN];
int n, heapSize, posSize;
void push(int x){
int i = ++heapSize;
while(i > 1 && A[Heap[i/2]] > x){
Heap[i] = Heap[i/2];
Pos[Heap[i]] = i;
i = i/2;
}
A[++posSize] = x;
Heap[i] = posSize;
Pos[Heap[i]] = i;
}
void pop(int x){
int i = Pos[x];
Heap[i] = Heap[heapSize--];
Pos[Heap[i]] = i;
int min, aux;
while(min != i){
if(2*i <= heapSize && A[Heap[2*i]] < A[Heap[i]])
min = 2*i;
else
min = i;
if(2*i+1 <= heapSize && A[Heap[2*i+1]] < A[Heap[min]])
min = 2*i + 1;
aux = Heap[min];
Heap[min] = Heap[i];
Heap[i] = aux;
Pos[Heap[i]] = i;
Pos[Heap[min]] = min;
}
}
int main(int argc, const char * argv[])
{
int op, x;
freopen("heapuri.in", "r", stdin);
freopen("heapuri.out", "w", stdout);
cin >>n;
for(int i = 1; i <= n; i++){
cin >> op;
if(op == 1){
cin >> x;
push(x);
}
else if (op == 2){
cin >> x;
pop(x);
}
else if(op == 3){
cout << A[Heap[1]] << endl;
}
}
}