#include <stdio.h>

void maxHeapify(int vetor[], int i, int n){
    int esq, dir, maior, temp;
    esq = 2*i + 1;
    dir = 2*i + 2;

    if(esq >= 1 && esq <=n && vetor[esq] > vetor[i]){
        maior = esq;
    }else{
        maior = i;
    }

    if(dir >= 1 && dir <= n && vetor[dir] > vetor[maior]){
        maior = dir;
    }

    if(maior !=i ){
        temp = vetor[i];
        vetor[i] = vetor[maior];
        vetor[maior] = temp;
        maxHeapify(vetor, maior, n);
    }
}

void buildMaxHeap(int vetor[], int n){
    int i;
    for(i=(n-1/2); i>=0 ; i--){
        maxHeapify(vetor, i, n-1);
    }
}

void heapSort(int vetor[], int n){
    int i, temp;
    buildMaxHeap(vetor, n);
    for(i=(n-1); i>=1; i--){
        temp = vetor[0];
        vetor[0] = vetor[i];
        vetor[i] = temp;
        maxHeapify(vetor, 0, i-1);
    }
}