Organizando dados em Heap e o Heapsort em c++ - Parte 2

    Continuando a publicação da semana passada, agora que já entendemos árvore, podemos falar de heap e heapsort. Apesar da introdução a árvores binárias, o heapsort é mais facilmente feito em um vetor, porém como ele segue a estrutura como se fosse uma árvore binária, é importante entender árvore antes de partir para o heap. Teremos 3 funções que vamos chamar de max_Heapify, build_Heap e o próprio Heapsort. As 2 primeiras vão servir para organizar tudo para que nosso vetor possa usar o Heapsort e ficar organizado do maior para o menor.
    Vamos começar com o Max-Heapify:

#include <iostream>

using namespace std;

void max_Heapify(int* vetor, int i, int tamVetor){
	int left = 2*i;
	int right = 2*i+1;
	int max;
	if(left <= tamVetor && vetor[left] > vetor[i] ){
		max = left;
	}
	else{
		max = i;
	}
	if(right <= tamVetor && vetor[right] > vetor[max]){
		max = right;
	}
	if(max != i){
		int aux = vetor[i];
		vetor[i] = vetor[max];
		vetor[max] = aux;
		max_Heapify(vetor,max,tamVetor);
	}
}
int main(){
	
}

    Em breve preencheremos o main, por hora deixemos ele vazio. Sobre a função do max_Heapify, temos o seguinte:
    Left e right são os filhos a esquerda e direita do nosso nó (Que no caso é nosso elemento no vetor) respectivamente. Em Heap, ao organizarmos um vetor, os filhos a esquerda e direita sempre serão 2*i e 2*i+1 onde i é a posição atual do nosso elemento no vetor. Como uma árvore de máximo de heap diz que o pai sempre deve ser maior que os seus filhos, nossa função de max_heapify nos garante que essa propriedade é sempre respeitada, e é ai que começam os ifs.
    Os ifs servem para checarmos se nosso elemento é realmente maior que seus filhos. Caso não seja, ele troca os elementos de posição e chama a função de novo, pois mesmo depois da troca, o elemento que antes era pai e se tornou filho pode ainda estar no lugar errado.

#include <iostream>

using namespace std;

void max_Heapify(int* vetor, int i, int tamVetor){
	int left = 2*i;
	int right = 2*i+1;
	int max;
	if(left <= tamVetor && vetor[left] > vetor[i] ){
		max = left;
	}
	else{
		max = i;
	}
	if(right <= tamVetor && vetor[right] > vetor[max]){
		max = right;
	}
	if(max != i){
		int aux = vetor[i];
		vetor[i] = vetor[max];
		vetor[max] = aux;
		max_Heapify(vetor,max,tamVetor);
	}
}

void build_Heap(int* vetor, int tamVetor){
	for(int i=tamVetor/2;i>=0;i--){
		max_Heapify(vetor,i,tamVetor);
	}
}
int main(){
	
}

    Como podemos ver a função de build_Heap é bem simples, ela apenas serve para chamarmos a função max_Heapify. Mas reparem que ela não percorre toda a árvore e apenas da metade até a raiz. Isso porque como o max_Heapify faz a chamada recursiva e vai corrigindo nossa árvore, nós só precisamos nos preocupar a partir da altura equivalente a metade dela! Impressionante, não?
    Por fim vamos ao nosso Heapsort!
    

#include <iostream>

using namespace std;

void max_Heapify(int* vetor, int i, int tamVetor){
	int left = 2*i;
	int right = 2*i+1;
	int max;
	if(left <= tamVetor && vetor[left] > vetor[i] ){
		max = left;
	}
	else{
		max = i;
	}
	if(right <= tamVetor && vetor[right] > vetor[max]){
		max = right;
	}
	if(max != i){
		int aux = vetor[i];
		vetor[i] = vetor[max];
		vetor[max] = aux;
		max_Heapify(vetor,max,tamVetor);
	}
}

void build_Heap(int* vetor, int tamVetor){
	for(int i=tamVetor/2;i>=0;i--){
		max_Heapify(vetor,i,tamVetor);
	}
}

void Heapsort(int* vetor, int tamVetor){
	build_Heap(vetor,tamVetor);
	for(int i=tamVetor;i>=1;i--){
		int aux = vetor[0];
		vetor[0] = vetor[i];
		vetor[i] = aux;
		tamVetor--;
		max_Heapify(vetor,0,tamVetor);
	}
}
int main(){
	int vetor[] = {4,1,3,2,16,9,10,14,8,7};
	Heapsort(vetor,10);
	for(int i=0;i<10;i++){
		cout << vetor[i] << " ";
	}
	cout << endl;
   // vetor ordenado: 1,2,3,4,7,8,9,10,14,16
}

    O Heapsort pode parecer um pouco esquisito ou redundante, mas eu vou explicar: Depois de construirmos nosso heap de máximo, nosso maior elemento está na primeira casa, mas como nossa ordenação é crescente, precisamos coloca-lo na ultima posição. Feito isso, diminuimos a variável que contem o tamanho do nosso vetor, para que desconsideremos a posição que colocamos o elemento, para que nosso max_heapify não acuse um erro no heap que não existe, já que o elemento não faz mais parte da árvore.
    Em seguida, chamamos o max_heapify para a nossa nova raiz, pois este elemento pode não ser o maior e estar na posição errada. Repetimos esse processo até que o nosso vetor fique completamente organizado!