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 
