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

#define MAX 20

void troca(int * a, int *b){
  int aux = *a;
  *a = *b;
  *b = aux;
}

void sobe_heap(int *heap, int pos){
  if(pos == 0) return;
  int pai = (pos-1)/2;
  //EXISTE UMA INVERSAO?
  if(heap[pos] > heap[pai]){
    troca(&(heap[pos]), &(heap[pai]));
    sobe_heap(heap, pai);
  }else{
    //Se não tem inversao nao faz nada.
  }
}

void insere(int *heap, int n, int valor){
  heap[n] = valor;
  sobe_heap(heap, n);
  return;
}

void desce_heap(int * heap, int n, int pos){
  int esq = 2*pos + 1;
  int dir = 2*pos + 2;
  
  //tenho filhos?
  if(esq >= n) return;
  
  int maior_filho = esq;
  
  //verifica se tem filho direito
  // e se ele é maior que o esquerdo
  if(dir < n && heap[dir] > heap[maior_filho]){
    maior_filho = dir;
  }
  
  //VERIFICAR SE heap[pos] é maior que O MAIOR  FILHO
  //se for troca
  if(heap[pos] < heap[maior_filho]){
    troca(&(heap[pos]), &(heap[maior_filho]));
    desce_heap(heap, n, maior_filho);
  }else{
    //se não tem troca, heap[pos] já tá no lugar certo.
  }
}


int extrair(int *heap, int n){
  int maior = heap[0];
  heap[0] = heap[n-1];
  desce_heap(heap, n-1, 0); 
  return maior;
}

void imprime(int *heap, int n){
  for(int i = 0; i < n; i++){
    printf("%d ", heap[i]); 
  }
  printf("\n");
}

//recebe um vetor qualquer, e transforma em um heap
void constroi_heap(int *v, int n){
    for(int i = n/2 ; i >= 0; i--){
      desce_heap(v, n, i);
    }
}

int main(int argc, char* argv[]){
  int * heap = (int*) malloc(sizeof(int)*MAX);
  int n = 0;
  
  insere(heap, n, 3);
  n++;
  imprime(heap, n);
  
  insere(heap, n, 10);
  n++;
  imprime(heap, n);
    
  insere(heap, n, 67);
  n++;
  imprime(heap, n);
  
  insere(heap, n, 15);
  n++;
  imprime(heap, n);
  
  int maior = extrair(heap, n);
  n--;
  printf("o maior é %d\n", maior);
  imprime(heap, n);
  
  maior = extrair(heap, n);
  n--;
  printf("o maior é %d\n", maior);
  imprime(heap, n);
  
  insere(heap, n, 80);
  n++;
  imprime(heap, n);
  
  maior = extrair(heap, n);
  n--;
  printf("o maior é %d\n", maior);
  imprime(heap, n);
  
  for(int i = 0; i < MAX; i++){
    heap[i] = rand()%100;
  }
  n = MAX;
  imprime(heap, n);
  
  constroi_heap(heap, n);
  imprime(heap, n);
    
  free(heap);
  return 0;
}