#include <stdio.h>

void intercambiar(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void heapify(int vector[], int n, int i) {

    int mayor = i;

    int hijoIzquierdo = 2 * i + 1;
    int hijoDerecho = 2 * i + 2;

    if (hijoIzquierdo < n &&
        vector[hijoIzquierdo] > vector[mayor]) {

        mayor = hijoIzquierdo;
    }

    if (hijoDerecho < n &&
        vector[hijoDerecho] > vector[mayor]) {

        mayor = hijoDerecho;
    }

    if (mayor != i) {

        intercambiar(&vector[i], &vector[mayor]);

        heapify(vector, n, mayor);
    }
}

void heapSort(int vector[], int n) {

    // Construir Max Heap
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(vector, n, i);
    }

    // Extraer elementos uno por uno
    for (int i = n - 1; i > 0; i--) {

        intercambiar(&vector[0], &vector[i]);

        heapify(vector, i, 0);
    }
}

void imprimir(int vector[], int n) {

    for (int i = 0; i < n; i++) {
        printf("%d ", vector[i]);
    }

    printf("\n");
}

int main() {

    int vector[] = {45, 12, 78, 34, 23, 9, 56};
    int n = 7;

    printf("Vector original:\n");
    imprimir(vector, n);

    heapSort(vector, n);

    printf("Vector ordenado:\n");
    imprimir(vector, n);

    return 0;
}