Max-Heap

#include <stdio.h>

/*
                        Criação e controle de MAX-HEAP
    Em uma arvore max-heap todos os elementos filhos são menores que os pais,
    em uma min-heap ocorro o contrário. Não há uma distinção de lados, ou seja,
    tanto o filho a direita quanto o à esquerda podem ser o maior, desde que não
    sejam maiores que o pai.
    Ex:
               CORRETO                          ERRADO
       (Filho menores que os pais)    (10 e 25 tem filhos maiores)
                 40                               40
              /     \                          /     \
           15        30                     10*       25*
          /  \      /  \                   /  \      /  \
        5     10  25    20               15    5   30    20

    Como o comportamento da heap é sempre igual, pode-se representar uma heap com
    um array.
*/



//Constante de capacidade total de armazenamento
#define CAPACITY 15

//Tamanho inicia em -1
int size = -1;

//Inicia Heap, colocando valor padrão de -1
void createHeap(int heap[]){
    for(int i = 0; i < CAPACITY;i++){
        heap[i] = -1;
    }
}

/*Retorna filho a esquerda
 *O filho a esquerda sempre será o dobro da posição + 1
*/
int getL(int pos){
    return (int) 2 * pos+1;
}

/*Retorna filho a direita
 *O filho a direita sempre será o dobro da posição + 2
*/
int getR(int pos){
    return (int) 2 * pos+2;
}

/*Retorna o pai
 *O pai sempre será metade da posição-1
*/
int getP(int pos){
    return (int) (pos-1)/2;
}

/*  Inverte os números nas posições x e y
    *Para ordenar uma heap será necessário fazer várias trocas
*/
void swap(int heap[],int x, int y){
    int aux = heap[x];
    heap[x] = heap[y];
    heap[y] = aux;
}

//Retona o maior elemento do heap
int getMax(int heap[]){
    if(size > -1){
        return heap[0];
    }else printf("Impossivel obter maior número, array vazio!\n");
}

/*  Após inserir um item é preciso ver se ele não é maior que seu pai,
    caso seja será necessário inverte-los de posição. Após a troca é preciso
    verificar novamente se o pai não é menor que filho até que não haja mais
    trocas para serem feitas.
*/
void heapfyUp(int heap[],int pos){
    
    //Caso não seja a raiz
    if(pos > 0){
        //Caso o pai seja menor que filho, faz a troca
        if(heap[getP(pos)] < heap[pos])
            swap(heap,getP(pos),pos);
            
        //Chama a função novamente agora passando a posição do pai
        heapfyUp(heap,getP(pos));
    }
}

/*  Para remover um elemento é preciso coloca-lo no final da lista para só depois 
    remove-lo. Após isso é necessário verificar se o elemento que foi trocado de
    lugar está corretamente posicionado, verificando se ele não é menor que os 
    seus filhos, caso seja ocorrem trocas até que a heap esteja correta.
*/
void heapfyDown(int heap[],int pos){
    
    //Verifica se o elemento não é uma folha
    if(heap[pos] > -1){
        //Se o pai for menor que o filho a esquerda
        if(heap[pos] < heap[getL(pos)]){
            //Faz a troca
            swap(heap,pos,getL(pos));
            //Chama a função para o filho a esquerda
            heapfyDown(heap,getL(pos));
        }
        
        //Se o pai for menor que o filho a direita
        if(heap[pos] < heap[getR(pos)]){
            //Faz a troca
            swap(heap,pos,getR(pos));
            //Chama a função para o filho a direita
            heapfyDown(heap,getR(pos));
        }
    }
}

//Insere valor e ordena
void insert(int n,int heap[]){
    //Aumenta o tamanho da heap
    size++;
    //Insere valor no final
    heap[size] = n;
    //Ordena a heap de baixo para cima
    heapfyUp(heap,size);
}

//Remove valor e ordena
void removeItem(int pos,int heap[]){
    //Coloca o valor a ser removido no final da heap
    swap(heap,pos,size);
    //Remove o item 
    heap[size] = -1;
    //Diminui o tamanho da heap
    size--;
    //Ordena a heap de cima para baixo
    heapfyDown(heap,0);
}

//Mostra valores inseridos
void show(int heap[]){

    printf("Heap: ");
    for(int i = 0; i <= size; i++){
        
        if(i < size)
            printf("%d - ",heap[i]);
        else
            printf("%d",heap[i]);
    }
   
}

int main(void) {

    int maxHeap[CAPACITY];
    createHeap(maxHeap);
    insert(5,maxHeap);
    insert(10,maxHeap);
    insert(15,maxHeap);
    insert(20,maxHeap);
    insert(25,maxHeap);
    insert(30,maxHeap);
    insert(35,maxHeap);
    show(maxHeap);
    printf("\nRemovendo 35...\n");
    removeItem(0,maxHeap);
    show(maxHeap);
    printf("\nAdicionando 40...\n");
    insert(40,maxHeap);
    show(maxHeap);
    
    
    return 0;
}