#include <stdio.h>

void criarHeap(int v[], int inicio, int final) {
    int aux = v[inicio];
    int filho = inicio * 2 + 1;
    while (filho <= final) {
        // Pai tem 2 filhos? Se sim, qual é o maior?
        if (filho < final && filho + 1 < final && v[filho] < v[filho + 1]) {
            filho++;
        }

        // Troca o filho com o pai se o filho for maior.
        if (aux < v[filho]) {
            v[inicio] = v[filho];
            inicio = filho;
            filho = 2 * inicio + 1;
        } else {
            filho = final + 1;
        }
    }
    v[inicio] = aux; // Pai troca com filho mais profundo mais a direita.
}

void heapSort(int v[], int tam) {
    int i;
    int aux;
    for (i = (tam - 1) / 2; i >= 0; i--) { // Cria o heap.
        criarHeap(v, i, tam - 1);
    }
    for (i = tam - 1; i >= 1; i--) { // Pega o maior elemento e coloca na posição o array.
        aux = v[0];
        v[0] = v[i];
        v[i] = aux;
        criarHeap(v, 0, i - 1); // Cria o heap sem o maior elemento anterior.
    }
}

int main(void) {
    int teste[] = {8, 4, 2, 9, 5, 0, 10, 7, 1, 3, 6};
    heapSort(teste, 11);
    for (int i = 0; i <= 10; i++) {
        printf("%i ", teste[i]);
    }
    return 0;
}