Lógica de Programação - Ordenação Heap Sort

 O algoritmo Heapsort consiste de duas fases

1. construir um Heap de um vetor arbitrário

2. usar o Heap para ordenar os dados

Heaps são árvores binárias. É importante deixar claro desde já que são árvores binárias, mas não são árvores binárias de pesquisa. Mais especificamente, duas propriedades definem o Heap:

1. O valor de um nó é maior ou igual ao valor de seus filhos;

2. O Heap é uma árvore binária completa ou quase-completa da esquerda para a direita.

A adição de um novo elemento sempre é feita na próxima posição livre do array. Essa estratégia garante que o Heap sempre será completo ou quase completo da esquerda para a direita.

Dado n números a serem ordenados

1. Coloque os dados em uma árvore binária

2. Repetir os seguintes passos, 

2.1. Verificar se um nó filho é menor que o pai, 

2.2 Se for, realize a troca

Vetor transformado em árvore binária

Árvore Binária (heap), após a troca de dados entre pais e filhos onde os filhos tenham valores maiores que os pais

Agora pegamos e eliminamos o maior valor da árvore (raiz) e jogamos na última casa do vetor, usamos heap para reorganizar os dados e refazemos o processo, pegando a nova raiz e colocando na penúltima posição do vetor.

Refazemos o processo até que a árvore esteja totalmente eliminada e o vetor ordenado

Código fonte:

Algoritmo "heapsort"  
 // Descrição  : Ordenação por heapsort  
 // Autor(a)  : Cléuber José  
 // Data atual : 22/12/2020  
 Const  
   TAM_VETOR=10  
 Var  
 // Seção de Declarações das variáveis   
    vet :vetor [1..TAM_VETOR] de inteiro  
    i,aux, filho: inteiro  
 procedimento mostrar_vetor()  
 inicio  
   escreval("")  
   escreval("------Dados do vetor------")  
   para i de 1 ate TAM_VETOR faca  
    escreva(vet[i]," ")  
   fimpara  
   escreval("")  
   escreval("--------------------------")  
 fimprocedimento  
 procedimento gerar_dados_vetor()  
 var  
   j:inteiro  
 inicio  
   para i de 1 ate TAM_VETOR faca  
    vet[i]<-i  
   fimpara  
   para i de 1 ate int(TAM_VETOR/2) passo 2 faca  
    aux<-vet[i]  
    vet[i]<-vet[TAM_VETOR+1-i]  
    vet[TAM_VETOR+1-i]<-aux  
   fimpara  
   para i de 1 ate int(TAM_VETOR/2) passo 1 faca  
    j<-randI(TAM_VETOR)+1  
    aux<-vet[i]  
    vet[i]<-vet[j]  
    vet[j]<-aux  
   fimpara  
 fimprocedimento  
 procedimento criar_heap(pai, tamanho:inteiro)  
 inicio  
   aux<-vet[pai]  
   filho<-pai*2  
   enquanto filho<=tamanho faca  
    se(filho <tamanho) entao  
      se vet[filho]<vet[filho+1] entao  
       filho<-filho+1  
      fimse  
    fimse  
    se aux<vet[filho] entao  
      vet[pai]<-vet[filho]  
      pai<-filho  
      filho<-2*pai  
    senao  
      filho<-tamanho+1  
    fimse  
   fimenquanto  
   vet[pai]<-aux  
 fimprocedimento  
 procedimento heap_sort()  
 inicio  
   escreval(int(TAM_VETOR/2))  
   para i de int(TAM_VETOR/2) ate 1 passo -1 faca  
    criar_heap(i,TAM_VETOR)  
   fimpara  
   para i de TAM_VETOR ate 2 passo -1 faca  
    aux<-vet[1]  
    vet[1]<-vet[i]  
    vet[i]<-aux  
    criar_heap(1, i-1)  
   fimpara  
 fimprocedimento  
 Inicio  
 // Seção de Comandos, procedimento, funções, operadores, etc...   
   escreval("---Ordenação por Heapsort---")  
   gerar_dados_vetor()  
   mostrar_vetor()  
   heap_sort()  
   mostrar_vetor()  
 Fimalgoritmo