malabarismo_de_malter.cpp

//
//  malabarismo_de_malter.cpp
//
//  Created by Lucca Siaudzionis on 17/05/15.
//
//  Malabarismo de Malter - Noic

#include <cstdio>
#include <algorithm>
using namespace std;

//---------------------
#define MAXN 1000100

int heap[MAXN];
int tamanho_heap;
//---------------------

int pai(int i){
    return i/2;
}

int esquerda(int i){
    return 2*i;
}

int direita(int i){
    return 2*i+1;
}

void heapify_up(int v){
    
    if(v == 1) return;
    
    int p = pai(v);
    if(heap[v] > heap[p]){
        swap(heap[v], heap[p]);
        
        heapify_up(p);
    }
    
}

void heapify_down(int v){
    
    int d = direita(v);
    int e = esquerda(v);
    
    int maior = v;
    
    if(d <= tamanho_heap && heap[d] > heap[maior]) maior = d;
    if(e <= tamanho_heap && heap[e] > heap[maior]) maior = e;
    
    if(maior != v){
        swap(heap[v], heap[maior]);
        
        heapify_down(maior);
    }
}

void insere(int valor){
    heap[++tamanho_heap] = valor;
    
    heapify_up(tamanho_heap);
}

void deleta(int posicao){
    
    swap(heap[posicao], heap[tamanho_heap]);
    tamanho_heap--;
    
    heapify_down(posicao);
}

int main(){
    
    int n;
    scanf("%d", &n);
    
    for(int i = 1;i <= n;i++){
        
        char operacao;
        scanf(" %c", &operacao);
        
        if(operacao == 'I'){ // inserir um número
            int valor;
            scanf("%d", &valor);
            
            insere(valor);
        }
        
        if(operacao == 'D'){
            printf("%d\n", heap[1]); // imprime o valor do topo
            deleta(1);
        }
        
    }
    
    return 0;
}