A ordenação por heap, conhecida como Heap Sort, é um algoritmo de ordenação baseado na estrutura de dados chamada heap. Um heap é uma árvore binária quase completa que satisfaz a propriedade de heap, onde o valor de cada nó filho é sempre menor (ou maior) que o valor de seu nó pai. Este método de ordenação pode ser considerado uma forma de ordenação por seleção que utiliza o conceito de heap. Existem dois tipos principais de heaps:
- Max-Heap (Heap de Máximos): Cada nó possui um valor maior ou igual ao de seus filhos. Utilizado para ordenar dados em ordem crescente.
- Min-Heap (Heap de Mínimos): Cada nó possui um valor menor ou igual ao de seus filhos. Utilizado para ordenar dados em ordem decrescente.
A complexidade de tempo média do Heap Sort é de O(n log n).
Princípios de Funcionamento
- Construção do Heap Inicial: O array de entrada é tratado como uma árvore binária quase completa. A partir do último nó não-folha, inicia-se um processo de "heapificação" (ajuste do heap) de trás para frente. Este processo compara o nó atual com seus filhos, trocando-o com o maior (ou menor) filho se necessário, e recursivamente aplica o ajuste ao filho que recebeu o valor trocado, até que a propriedade de heap seja satisfeita para aquele nó e seus descendentes. Isso resulta em um heap inicial onde o maior (ou menor) elemento está na raiz.
- Processo de Ordenação: O elemento no topo do heap (a raiz, que é o maior ou menor elemento) é trocado com o último elemento da parte não ordenada do array. A parte ordenada do array cresce e a parte não ordenada encolhe. Após a troca, o novo elemento na raiz é "heapificado" para baixo para restaurar a propriedade de heap na subárvore restante. Este processo é repetido até que todos os elementos estejam na sua posição final, resultando no array ordenado.
Passos do Algoritmo
- Construa um heap (Max-Heap para ordem crescente, Min-Heap para decrescente) a partir do array de entrada.
- Troque o elemento raiz do heap (o maior ou menor) com o último elemento do heap.
- Reduza o tamanho do heap em um (o elemento agora no final está na sua posição final).
- Restaurar a propriedade de heap para o novo topo do heap (o primeiro elemento), chamando a função de ajuste (heapify) para a raiz.
- Repita os passos 2 a 4 até que o tamanho do heap seja 1.
Exemplos de Código
C
#include <stdio.h>
// Função para ajustar um sub-heap no vetor, garantindo a propriedade de Max-Heap
void ajustarHeap(int vetor[], int tamanho, int indiceRaiz) {
int maiorElemento = indiceRaiz; // Inicializa o maior como a raiz
int filhoEsquerdo = 2 * indiceRaiz + 1; // Índice do filho esquerdo
int filhoDireito = 2 * indiceRaiz + 2; // Índice do filho direito
// Se o filho esquerdo for maior que a raiz
if (filhoEsquerdo < tamanho && vetor[filhoEsquerdo] > vetor[maiorElemento])
maiorElemento = filhoEsquerdo;
// Se o filho direito for maior que o maiorElemento atual
if (filhoDireito < tamanho && vetor[filhoDireito] > vetor[maiorElemento])
maiorElemento = filhoDireito;
// Se o maiorElemento não for a raiz
if (maiorElemento != indiceRaiz) {
// Troca a raiz com o maiorElemento
int temp = vetor[indiceRaiz];
vetor[indiceRaiz] = vetor[maiorElemento];
vetor[maiorElemento] = temp;
// Recursivamente ajusta a sub-árvore afetada
ajustarHeap(vetor, tamanho, maiorElemento);
}
}
// Função principal de ordenação por heap
void ordenarHeap(int vetor[], int tamanho) {
// Constrói o Max-Heap (reorganiza o array)
// Começa do último nó não-folha
for (int i = tamanho / 2 - 1; i >= 0; i--)
ajustarHeap(vetor, tamanho, i);
// Extrai elementos um por um do heap
for (int i = tamanho - 1; i >= 0; i--) {
// Move a raiz atual para o final
int temp = vetor[0];
vetor[0] = vetor[i];
vetor[i] = temp;
// Chama ajustarHeap na sub-árvore reduzida
ajustarHeap(vetor, i, 0);
}
}
// Função para imprimir o vetor
void imprimirVetor(int vetor[], int tamanho) {
for (int i = 0; i < tamanho; i++)
printf("%d ", vetor[i]);
printf("\n");
}
int main() {
int dados[] = {12, 11, 13, 5, 6, 7};
int n = sizeof(dados) / sizeof(dados[0]);
printf("Vetor original: ");
imprimirVetor(dados, n);
ordenarHeap(dados, n);
printf("Vetor ordenado: ");
imprimirVetor(dados, n);
return 0;
}
C++
#include <iostream>
#include <vector>
#include <algorithm> // Para std::swap
// Função auxiliar para manter a propriedade de Max-Heap em uma sub-árvore
void aplicarHeapify(std::vector<int>& dados, int limite, int indiceAtual) {
int maior = indiceAtual; // Assume que o nó atual é o maior
int filhoEsquerdo = 2 * indiceAtual + 1;
int filhoDireito = 2 * indiceAtual + 2;
// Verifica se o filho esquerdo existe e é maior que o atual maior
if (filhoEsquerdo < limite && dados[filhoEsquerdo] > dados[maior]) {
maior = filhoEsquerdo;
}
// Verifica se o filho direito existe e é maior que o atual maior
if (filhoDireito < limite && dados[filhoDireito] > dados[maior]) {
maior = filhoDireito;
}
// Se o maior não é o nó atual, realiza a troca e continua a ajustar
if (maior != indiceAtual) {
std::swap(dados[indiceAtual], dados[maior]);
aplicarHeapify(dados, limite, maior); // Recursão para a sub-árvore afetada
}
}
// Função principal de ordenação Heap Sort
void heapSort(std::vector<int>& dados) {
int n = dados.size();
// Constrói um Max-Heap (reorganiza o vetor)
// O loop começa do último nó não-folha e vai até a raiz
for (int i = n / 2 - 1; i >= 0; i--) {
aplicarHeapify(dados, n, i);
}
// Extrai elementos um por um do heap
// Troca o elemento raiz (maior) com o último elemento do heap
// Reduz o tamanho do heap e ajusta novamente a raiz
for (int i = n - 1; i > 0; i--) {
std::swap(dados[0], dados[i]); // Move a raiz atual para o final
aplicarHeapify(dados, i, 0); // Chama aplicarHeapify no heap reduzido
}
}
int main() {
std::vector<int> meuVetor = {9, 7, 5, 11, 12, 2, 14, 10};
std::cout << "Vetor antes da ordenação: ";
for (int x : meuVetor) {
std::cout << x << " ";
}
std::cout << std::endl;
heapSort(meuVetor);
std::cout << "Vetor após a ordenação: ";
for (int x : meuVetor) {
std::cout << x << " ";
}
std::cout << std::endl;
return 0;
}
Java
public class HeapSorter {
/**
* Implementa o algoritmo Heap Sort para ordenar um array de inteiros.
* @param array O array de inteiros a ser ordenado.
*/
public static void sortArray(int[] array) {
int tamanho = array.length;
// Fase 1: Construção do Max-Heap.
// Itera de trás para frente, começando do último nó não-folha.
for (int i = tamanho / 2 - 1; i >= 0; i--) {
maintainHeapProperty(array, tamanho, i);
}
// Fase 2: Extração dos elementos do heap, um por um.
// O maior elemento (raiz) é movido para o final do array.
for (int i = tamanho - 1; i > 0; i--) {
// Troca o elemento raiz (maior) com o último elemento do heap atual.
int temp = array[0];
array[0] = array[i];
array[i] = temp;
// Chama a função para manter a propriedade de heap no array reduzido.
// O elemento recém-colocado na raiz precisa ser "empurrado para baixo".
maintainHeapProperty(array, i, 0);
}
}
/**
* Função auxiliar para ajustar um sub-heap no array, garantindo a propriedade de Max-Heap.
* @param array O array onde o heap está armazenado.
* @param limite O tamanho atual do heap (a parte não ordenada do array).
* @param indiceRaiz O índice do nó raiz da sub-árvore a ser ajustada.
*/
private static void maintainHeapProperty(int[] array, int limite, int indiceRaiz) {
int maiorIndice = indiceRaiz; // Assume que a raiz é o maior
int filhoEsquerdo = 2 * indiceRaiz + 1; // Índice do filho esquerdo
int filhoDireito = 2 * indiceRaiz + 2; // Índice do filho direito
// Verifica se o filho esquerdo existe e é maior que o elemento no maiorIndice.
if (filhoEsquerdo < limite && array[filhoEsquerdo] > array[maiorIndice]) {
maiorIndice = filhoEsquerdo;
}
// Verifica se o filho direito existe e é maior que o elemento no maiorIndice.
if (filhoDireito < limite && array[filhoDireito] > array[maiorIndice]) {
maiorIndice = filhoDireito;
}
// Se o maior elemento não é a raiz, realiza a troca e recursivamente ajusta a sub-árvore.
if (maiorIndice != indiceRaiz) {
int swapTemp = array[indiceRaiz];
array[indiceRaiz] = array[maiorIndice];
array[maiorIndice] = swapTemp;
maintainHeapProperty(array, limite, maiorIndice); // Recursão
}
}
public static void main(String[] args) {
int[] meuArray = {4, 10, 3, 5, 1, 9, 8};
System.out.print("Array original: ");
for (int num : meuArray) {
System.out.print(num + " ");
}
System.out.println();
sortArray(meuArray);
System.out.print("Array ordenado: ");
for (int num : meuArray) {
System.out.print(num + " ");
}
System.out.println();
}
}
Vantagens do Heap Sort
- Eficiência Consistente: Apresenta uma complexidade de tempo O(n log n) nos casos médio, melhor e pior, tornando-o previsível e robusto para grandes volumes de dados.
- Uso Mínimo de Espaço Auxiliar: O algoritmo é in-loco (in-place), o que significa que realiza a ordenação diretamente no array de entrada, necessitando apenas de um espaço auxiliar constante O(1).
Desvantagens do Heap Sort
- Instabilidade: O Heap Sort é um algoritmo de ordenação instável. Isso significa que a ordem relativa de elementos com valores iguais não é necessariamente preservada após a ordenação.
- Ineficiência de Cache: Devido aos seus padrões de acesso a memória serem menos sequenciais (salto entre nós pai e filho), pode não aproveitar tão bem o cache da CPU quanto outros algoritmos como o Merge Sort ou Quicksort, resultando em desempenho ligeiramente ifnerior para certas cargas de trabalho.
- Desempenho Relativo para Pequenos Dados: Embora sua complexidade assintótica seja excelente, as constantes envolvidas podem torná-lo um pouco mais lento que o Quicksort ou o Insertion Sort para conjuntos de dados de tamanho pequeno a médio.