#include <stdio.h>

int criarHeapRecursao(int v[], int inicio, int aux, int filho, int final) {
    if (filho > final) return inicio;
    
    // 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;
    }
    return criarHeapRecursao(v, inicio, aux, filho, final);
}

void criarHeap(int v[], int inicio, int final) {
    int aux = v[inicio];
    int filho = inicio * 2 + 1;
    inicio = criarHeapRecursao(v, inicio, aux, filho, final);
    v[inicio] = aux; // Pai troca com filho mais profundo mais a direita.
}

void heapSort1(int v[], int i, int tam) {
    if (i < 0) return;
    criarHeap(v, i, tam - 1);
    heapSort1(v, i - 1, tam);
}

void heapSort2(int v[], int i, int tam) {
    if (i <= 0) return;
    int aux = v[0];
    v[0] = v[i];
    v[i] = aux;
    criarHeap(v, 0, i - 1); // Cria o heap sem o maior elemento anterior.
    heapSort2(v, i - 1, tam);
}

void heapSort(int v[], int tam) {
    heapSort1(v, (tam - 1) / 2, tam);
    heapSort2(v, tam - 1, tam);
}

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;
}