Heap sort

/*
ALGORITMO MAX HEAP SORT
*/

#include <stdio.h>
#include <math.h>
/*
  Define tamanho maximo do array de dados
*/
#define SIZE 8

/* Declaração de funções e procedimentos */
int potencia();         /* Função que calcula a quantidade de nós em cada nível da árvore (2^p), send p o nível atual */
void populateVector();  /* Procedimento que preenche a estrutura de dados com números não sequenciais */
void showVector();      /* Procedimento que mostra na tela o conteúdo da estrutura de dados */
void maxHeapify();      /* Procedimento que ordena a árvore de acordo com as características de uma estrutura HEAP */
void heapSort();        /* Procedimento que percorre a estrutura de dados n vezes, de acordo com o tamanho atual da mesma */
void drawLevel();       /* Procedimento que desenha o nível atual da estrutura Heap */
void positionNode();    /* Procedimento que posiciona o cursor na posição determinada da estrutura Heap */
void showHeapDataStructure(); /* Procedimento que apresenta em forma de árvore a Estrutura Heap do vetor */

/* Declaração da variável que cria o vector de dados com o tamanho determinado */
int data[SIZE];
int main(void) {
    populateVector();
    printf("CHAOTIC DATA:\n");
    showVector();
    heapSort();
    return 0;
}

void populateVector(){
    /*
      Considera-se a posição inicial do vetor de dados com o indice a 1
    */
    for(int i = 1; i <= SIZE; i ++){
       scanf("%d",&data[i]);
    }
}

void maxHeapify(int i, int size){
           int childRight, childLeft, tmp, parent;
           parent = i;
           if (2 * i + 1 <= size)
             /*
               Pai com os dois filhos
             */
             {
                  childLeft = 2 * i;
                  childRight = 2 * i + 1;
                  if  (data[childLeft] >= data[childRight] &&
                       data[childLeft] > data[i])
                        parent = childLeft;
                  else if (data[childRight] >= data[childLeft] &&
                       data[childRight] > data[i])
                        parent = childRight;
            }
            else if (2 * i <= size)
               /*
                 Pai somente com o filho da esquerda
               */
            {
                 childLeft= 2 * i;
                 if (data[childLeft] > data[i])
                         parent = childLeft;

            }

          if (parent != i )
          {
               /*
                  Primeira fase: Neste momento ocorre a troca (swap) das posições da sub-arvore, sendo o maior
                  assumindo a posição de pai
               */

               tmp = data[i];
               data[i] = data[parent];
               data[parent] = tmp;
               maxHeapify(parent, size);
           }
}

void heapSort(){
       int size = SIZE;
       int tmp;
       for (; size >=2; size --){
          for(int i = size/2; i >= 1; i--){
              maxHeapify(i, size);
          }
          printf("\nMAX-HEAP DATA STRUCTURE\n");
          showVector();
          printf("\t\t\t\t\t\t\tRaiz\t\t\t\t  Nivel\n");
          showHeapDataStructure(size);

          /*
            Segunda fase: Na primeira execução, o maior (raiz da árvore binária) se desloca para a ultima posição
            do vector de dados. Na segunda execução, o maior vai pra penúltima posição, e assim, sucessivamente, até o
            vector se reduzir à duas posições.
          */

          tmp = data[size];
          data[size] = data[1];
          data[1] = tmp;
          if (size == 2) {
              printf("\nFULLY ORDINATED DATA \n");
              showVector(); }
      }
}

void showVector(){
   for(int i = 1; i <= SIZE; i ++){
        printf("[%d]\t", data[i]);
   }
   printf("\n\n");
}

void showHeapDataStructure(int size){

   // mostrar arvore binaria
   int p = 0;
   int tabIni = 7;
   int tabAtual = 7;
   int maxInLineNode = potencia(0);
   int inLineNode = 0;
   int maxLevel = (int) log2(size);
   positionNode(tabAtual);
   for(int i = 1; i <= size; i++){

      printf("[%d]", data[i]);
      inLineNode ++;
      printf("\t");
      tabAtual++;
      if (tabAtual == 7){ /* Divisão dos lados da árvore */
         printf("\t");  tabAtual++; }

     if (inLineNode == maxInLineNode) {
          inLineNode = 0;
          drawLevel(tabAtual, p);
          p++;
          if (p<=2)
             tabIni--;
          else
             tabIni -= 2;
          printf("\n");
          tabAtual = tabIni;
          positionNode(tabAtual);
     }
     if (p == maxLevel)  {// ultimo nivel
             inLineNode = 0;
             maxInLineNode = size - i;}
           //  printf("Size: %d, i: %d", size, i);}
     else
            maxInLineNode = potencia(p);
   }

}

int potencia(int p){
    int pot = 1;
    for(int i = 0; i < p; i++)
        pot *= 2;
    return pot;
}
void positionNode(int tab) {
    for (int i = 0; i < tab; i++)
            printf("\t");
}

void drawLevel(int tab, int p) {
     for(int i = 0; i <= (12 - tab); i ++) {
           printf("\t");
      }
      printf("%d", p);
}

/* the end */