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

#define MAX 100

typedef struct fp{
  int *dados; //o dado eh a propria chave
  int n, tamanho; //n numero atual, tamanho eh o numero maximo
} FP;

typedef FP * p_fp;

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

p_fp criar_fila_prio(int tamanho){
  p_fp f = (p_fp) malloc(sizeof(FP));
  f->dados = (int*) malloc(tamanho * sizeof(int));
  f->n = 0;
  return f;
}

void imprime_vetor(int *v, int n){
  for (int i = 0; i < n; i++){
    printf("%d ", v[i]);
  }
  printf("\n");
}
void sobe_heap(p_fp f, int pos){
  if(pos == 0){
    //RAIZ NAO SOBE 
    return;
  }
  int pai = (pos-1) / 2;
  printf("O pai do dados[%d] = %d eh o dados[%d] = %d\n", pos, f->dados[pos], pai, f->dados[pai]);
  if(f->dados[pai] < f->dados[pos]){
    //TENHO UMA INVERSAO
    troca(&(f->dados[pai]), &(f->dados[pos]));
    sobe_heap(f, pai);
  }
  //senao nao faz nada
}

void insere(p_fp f, int dado){ //necessario verifica se nao esta cheio
  f->dados[f->n] = dado;
  f->n = f->n + 1;
  sobe_heap(f, f->n - 1);
  return;
}

void desce_heap(p_fp f, int pos){ 
  printf("Descendo dados[%d] = %d\n", pos, f->dados[pos]);
  int esq = 2 * pos + 1;
  int dir = 2 * pos + 2;
  int maior_filho = -1;
  
  if(esq >= f->n){
    //ja sou uma folha
    return;
  }else{
    //suponho que o maior eh o esquerdo
    maior_filho = esq;
  }
  
  if(dir < f->n && f->dados[dir] > f->dados[esq]){
    //descobri que o direito eh maior
    maior_filho = dir;
  }
  
  //comparar e trocar com o maior
  if(f->dados[pos] < f->dados[maior_filho]){
    troca(&(f->dados[pos]), &(f->dados[maior_filho]));
    desce_heap(f, maior_filho);
  }
  
}

int extrai_maximo(p_fp f){  //necessario verifica se nao esta vazio
  int res = f->dados[0];
  troca(&(f->dados[0]), &(f->dados[f->n-1]));
  f->n = f->n - 1;
  desce_heap(f, 0);
  return res;
}

void mudar_prioridade(p_fp f, int pos, int nova_prio){
  if(nova_prio > f->dados[pos]){
    //aumentando a prioridade
     f->dados[pos] = nova_prio;
     sobe_heap(f, pos);
  }else{
    //diminui a prioridade
     f->dados[pos] = nova_prio;
     desce_heap(f, pos);
  }
}

int main(int argc, char * argv[]){
  
  p_fp f = criar_fila_prio(MAX);
  
  insere(f, 15);
  imprime_vetor(f->dados, 1);
  insere(f, 20);
  imprime_vetor(f->dados, 2);
  insere(f, 10);
  imprime_vetor(f->dados, 3);
  insere(f, 21);
  imprime_vetor(f->dados, 4);
  
  //aumentando a prioridade do 10 para 100
  mudar_prioridade(f, 2, 100);
  imprime_vetor(f->dados, 4);  
  
  //diminuir a prioridade do 100 para 1
  mudar_prioridade(f, 0, 1);
  imprime_vetor(f->dados, 4);  


  printf("O proximo da Fila de Prioridade e %d\n", extrai_maximo(f)); //extrai 21
  imprime_vetor(f->dados, 3);
  
  printf("O proximo da Fila de Prioridade e %d\n", extrai_maximo(f));
  imprime_vetor(f->dados, 2);
  printf("O proximo da Fila de Prioridade e %d\n", extrai_maximo(f));
  imprime_vetor(f->dados, 1);
  printf("O proximo da Fila de Prioridade e %d\n", extrai_maximo(f)); 
  
 
  return 0;
}