Heap Sort
Introdução
O Heap Sort é um algoritmo de ordenação eficiente baseado na estrutura de dados
heap. Ele tem complexidade O(n log n) tanto no pior caso quanto no caso médio,
tornando-se uma das opções mais estáveis para grandes conjuntos de dados. Esse
algoritmo funciona construindo um heap máximo (max heap) ou heap mínimo (min
heap) e, em seguida, removendo iterativamente os elementos da raiz para obter uma
lista ordenada.
O que é um Heap?
Um heap é uma árvore binária completa onde cada nó pai satisfaz a propriedade de
heap, que pode ser de dois tipos:
1. Max Heap: A chave de cada nó é maior ou igual às chaves de seus filhos.
2. Min Heap: A chave de cada nó é menor ou igual às chaves de seus filhos.
O Heap Sort normalmente usa um Max Heap para ordenar elementos em ordem
crescente.
Funcionamento do Heap Sort
O algoritmo é dividido em duas fases principais:
1. Construção do Heap: O vetor original é reorganizado para satisfazer a
propriedade de um Max Heap.
2. Ordenação: O maior elemento (raiz do heap) é movido para o final do vetor, e o
heap é reajustado (heapify) para manter a propriedade do heap.
Passo a Passo do Heap Sort
1. Construir o Max Heap
Para construir o heap, convertemos o vetor desordenado em um Max Heap. Isso é feito
percorrendo os nós de baixo para cima e ajustando a estrutura.
2. Extrair elementos do Heap
Depois que o heap é criado, a raiz (o maior elemento) é trocada com o último elemento
do vetor. O heap é então reduzido em tamanho e a operação heapify é chamada
novamente para manter a propriedade do heap.
Implementação do Heap Sort em C
A seguir, apresentamos a implementação do Heap Sort em C:
#include <stdio.h>
// Função para reorganizar um heap
void heapify(int arr[], int n, int i) {
int maior = i; // Inicializa o maior como raiz
int esquerda = 2 * i + 1;
int direita = 2 * i + 2;
// Se o filho da esquerda for maior que a raiz
if (esquerda < n && arr[esquerda] > arr[maior])
maior = esquerda;
// Se o filho da direita for maior que o maior até agora
if (direita < n && arr[direita] > arr[maior])
maior = direita;
// Se o maior não for a raiz
if (maior != i) {
int temp = arr[i];
arr[i] = arr[maior];
arr[maior] = temp;
// Chamada recursiva para ajustar o heap
heapify(arr, n, maior);
}
// Função principal do Heap Sort
void heapSort(int arr[], int n) {
// Constrói o heap (reorganiza o array)
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
// Extrai os elementos do heap um por um
for (int i = n - 1; i > 0; i--) {
// Move a raiz para o final
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
// Chama heapify na raiz reduzida
heapify(arr, i, 0);
}
// Função para imprimir um array
void imprimirArray(int arr[], int n) {
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
// Programa principal
int main() {
int arr[] = {12, 11, 13, 5, 6, 7};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Array original:\n");
imprimirArray(arr, n);
heapSort(arr, n);
printf("Array ordenado:\n");
imprimirArray(arr, n);
return 0;
Explicação do Código
1. Função heapify:
o Mantém a propriedade do Max Heap.
o Compara a raiz com seus filhos e troca caso necessário.
o Chama-se recursivamente até que a propriedade do heap seja satisfeita.
2. Função heapSort:
o Constrói o heap chamando heapify do meio do array até a raiz.
o Extrai elementos da raiz um por um, reorganizando o heap com heapify.
3. Função imprimirArray:
o Imprime os elementos do array para visualizar o processo de ordenação.
4. Função main:
o Define um array de exemplo.
o Chama heapSort e imprime os resultados.
Complexidade do Heap Sort
Caso Complexidade
Melhor caso O(n log n)
Caso médio O(n log n)
Pior caso O(n log n)
O motivo da complexidade O(n log n) é que cada inserção e remoção de um nó no heap
custa O(log n) e há n elementos no array.
Vantagens e Desvantagens do Heap Sort
Vantagens:
• Complexidade garantida de O(n log n), mesmo no pior caso.
Não requer memória extra significativa (ordenação in-place).
Bom desempenho para grandes volumes de dados.
Desvantagens:
• Não é estável (a ordem relativa de elementos iguais pode mudar).
Maior número de operações de troca em comparação com Quick Sort,
podendo torná-lo mais lento na prática.
Conclusão
O Heap Sort é um algoritmo eficiente e confiável para ordenação de grandes conjuntos
de dados. Seu uso da estrutura heap garante uma ordenação consistente de O(n log n),
independentemente da entrada. Embora não seja o mais rápido na prática devido às
trocas constantes, sua confiabilidade e o fato de ser in-place o tornam uma excelente
opção quando o pior caso do Quick Sort pode ser um problema.
