Heap Sort

O Heap Sort é um algoritmo de ordenação que, para efetuar a ordenação de um vetor, considera uma estrutura chamada heap. Um heap pode ser representado por um nó com dois filhos: o filho à esquerda (filhoEsq) e o filho à direita (filhoDir). Para satisfazer a condição de heap, elemento nó, também chamado de pai, deve ter valor maior que seus filhos. Se essa condição não for satisfeita, os valores das posições devem ser alterados.

Vamos entender o código:

void constroiHeap(int v[], int tam, int pai) {
    int fEsq, fDir, maior;

    /* Definir os elementos maior, filho à esquerda e filho à direita */
    maior = pai;
    fEsq = 2 * pai + 1; 
    fDir = 2 * pai + 2; 

    /* Verificar quem é o maior elemento: o pai ou os filhos */
    if (fEsq < tam && v[fEsq] > v[maior]) {
            maior = fEsq;               
    }
    if (fDir < tam && v[fDir] > v[maior]) {
        maior = fDir;        
    }
    
    /* Se o pai não era o maior elemento, troque as posições e construa o heap */
    if (maior != pai) {
        trocar(&v[pai], &v[maior]);
        constroiHeap(v, tam, maior);
    }
}

void heapSort(int v[], int tam){
    for (int i = (tam / 2) - 1; i >= 0; i--) {
        constroiHeap(v, tam, i);
    }

    for (int i = tam - 1; i > 0; i--) { 
        trocar(&v[0], &v[i]);   
        constroiHeap(v, i, 0);      
    }
}

Na função heapSort, o primeiro laço de repetiçaõ marca a fase de construção do heap. O algoritmo percorre o vetor a ser ordenado e transforma-o em um heap válido, garantindo que cada nó pai seja maior que seus filhos. Isso é feito através da função constroiHeap.

Na segunda fase, marcada pelo segundo laço de repetição, o algoritmo realiza a ordenação propriamente dita. Ele extrai o maior elemento do heap, que está na raiz, e o coloca na posição correta no vetor ordenado. Em seguida, ajusta o heap para manter a propriedade de heap e repete o processo até que todos os elementos tenham sido ordenados.