#include <stdio.h>
#include <stdlib.h>
#define n 6

void criaHeap(int *v, int ini, int fim);
void heapSort(int *v);


int main()
{
    int i;
    int vet[n];

    for (i=0; i<n; i++)
    {
        printf("Informe um numero: \n");
        scanf("%d", &vet[i]);
    }

    for (i=0; i<n; i++)
    {
        printf("Numero: %d \n", vet[i]);
    }

    heapSort(vet);

    for (i=0; i<n; i++)
    {
        printf("Numero: %d \n", vet[i]);
    }
    return 0;
}

void criaHeap(int *v, int ini, int fim){
    int aux, i, j;
    i = ini;
    aux = v[i]; //guarda o pai
    j = 2 * i + 1; //calcula filho da esquerda
    while (j <= fim) {
        if (j < fim) { //pai tem dois filhos?
            if (v[j] < v[j+1]) //filho da direita é maior
                j++;
        }
        if (aux < v[j]) {
            //filho é maior que o pai
            v[i] = v[j];
            i = j;
            j = 2 * i + 1;
        }
        else {
            j = fim + 1;
        }
    }
    //antigo pai ocupa o lugar do último filho analisado
    v[i] = aux;
}

void heapSort(int *v){
    int i, aux;
    //criando a heap
    for (i=(n-1)/2; i>=0; i--) {
        criaHeap(v, i, n-1);
    }

    //ordenando
    for (i=n-1; i>=1; i--) {
        aux = v[0];
        v[0] = v[i];
        v[i] = aux;
        criaHeap(v, 0, i-1);
    }
}