--- title: "Heap Sort em Rust" url: "https://rustlang.com.br/algoritmos/heap-sort/" markdown_url: "https://rustlang.com.br/algoritmos/heap-sort.MD" description: "Aprenda Heap Sort em Rust com diagramas visuais de heap, processo heapify passo a passo, análise Big-O e código completo." date: "2026-02-24" author: "Equipe Rust Brasil" --- # Heap Sort em Rust Aprenda Heap Sort em Rust com diagramas visuais de heap, processo heapify passo a passo, análise Big-O e código completo. O **Heap Sort** (ordenação por heap) é um algoritmo de ordenação baseado na estrutura de dados **heap binário**. Ele funciona em duas fases: primeiro constrói um max-heap a partir do vetor, e depois extrai repetidamente o maior elemento (raiz do heap) e o coloca na posição final. O resultado é um vetor ordenado em ordem crescente. O Heap Sort combina duas propriedades importantes: é **in-place** (O(1) de espaço extra) e tem complexidade **O(n log n) garantida** em todos os casos. Diferente do Quick Sort, nunca degrada para O(n²). Diferente do Merge Sort, não precisa de memória extra. No entanto, na prática costuma ser mais lento que ambos devido ao seu padrão de acesso à memória desfavorável ao cache. O Rust oferece a estrutura `BinaryHeap` na biblioteca padrão, que implementa um max-heap eficiente. ## Como Funciona ### Conceitos de Heap Binário Um **heap binário máximo (max-heap)** é uma árvore binária completa onde cada nó é maior ou igual aos seus filhos. Ele pode ser representado em um vetor onde, para o nó no índice `i`: - Filho esquerdo: `2*i + 1` - Filho direito: `2*i + 2` - Pai: `(i - 1) / 2` ```text Vetor: [82, 43, 38, 27, 9, 3, 10] Índice: 0 1 2 3 4 5 6 Árvore correspondente: 82 (0) / \ 43 (1) 38 (2) / \ / \ 27 (3) 9 (4) 3 (5) 10 (6) Propriedade: todo pai ≥ seus filhos 82 ≥ 43, 38 ✓ 43 ≥ 27, 9 ✓ 38 ≥ 3, 10 ✓ ``` ### Processo Completo ```text Vetor inicial: [4, 10, 3, 5, 1] === FASE 1: Construir Max-Heap === Árvore inicial (NÃO é heap): 4 / \ 10 3 / \ 5 1 Heapify de baixo para cima (começar no último nó pai, índice 1): Passo 1: heapify(índice 1) — nó 10 10 > 5 e 10 > 1 → já é heap local ✓ 4 / \ 10 3 / \ 5 1 Passo 2: heapify(índice 0) — nó 4 4 < 10 → trocar com 10 4 < 5 → trocar com 5 10 10 / \ → / \ 4 3 5 3 / \ / \ 5 1 4 1 Max-Heap construído: [10, 5, 3, 4, 1] === FASE 2: Extrair Elementos === Passo 1: trocar raiz (10) com último, heapify [10, 5, 3, 4, 1] → swap(0,4) → [1, 5, 3, 4, |10] Heapify: [5, 4, 3, 1, |10] 5 / \ 4 3 / 1 10 (posição final) Passo 2: trocar raiz (5) com último não-fixo, heapify [5, 4, 3, 1, |10] → swap(0,3) → [1, 4, 3, |5, 10] Heapify: [4, 1, 3, |5, 10] 4 / \ 1 3 5 10 (posições finais) Passo 3: trocar raiz (4) com último não-fixo, heapify [4, 1, 3, |5, 10] → swap(0,2) → [3, 1, |4, 5, 10] Heapify: [3, 1, |4, 5, 10] Passo 4: trocar raiz (3) com último não-fixo [3, 1, |4, 5, 10] → swap(0,1) → [1, |3, 4, 5, 10] Resultado: [1, 3, 4, 5, 10] ✓ ``` ## Complexidade | Caso | Tempo | Espaço | |------|-------|--------| | Melhor | O(n log n) | O(1) | | Médio | O(n log n) | O(1) | | Pior | O(n log n) | O(1) | - **Tempo O(n log n) em todos os casos:** a construção do heap é O(n) (não O(n log n) como parece). A extração de n elementos, cada um com heapify O(log n), resulta em O(n log n). - **Construção do heap em O(n):** embora cada heapify individual seja O(log n), a maioria dos nós está perto das folhas. A soma telescópica resulta em O(n). - **Espaço O(1):** algoritmo totalmente in-place. O heap é construído diretamente no vetor de entrada. - **Instável:** a troca entre raiz e último elemento pode alterar a ordem relativa de elementos iguais. ## Implementação em Rust ```rust /// Heap Sort genérico. /// Ordena o slice in-place em ordem crescente usando um max-heap. fn heap_sort(vetor: &mut [T]) { let n = vetor.len(); if n <= 1 { return; } // Fase 1: Construir max-heap // Começar do último nó pai (n/2 - 1) até a raiz (0) for i in (0..n / 2).rev() { heapify(vetor, n, i); } // Fase 2: Extrair elementos do heap // Trocar a raiz (maior) com o último elemento // e restaurar a propriedade heap for fim in (1..n).rev() { vetor.swap(0, fim); heapify(vetor, fim, 0); } } /// Restaura a propriedade max-heap para a subárvore com raiz no índice `raiz`. /// `tamanho` é o número de elementos válidos no heap. fn heapify(vetor: &mut [T], tamanho: usize, raiz: usize) { let mut maior = raiz; let esquerdo = 2 * raiz + 1; let direito = 2 * raiz + 2; // Verificar se o filho esquerdo é maior que a raiz if esquerdo < tamanho && vetor[esquerdo] > vetor[maior] { maior = esquerdo; } // Verificar se o filho direito é maior que o maior até agora if direito < tamanho && vetor[direito] > vetor[maior] { maior = direito; } // Se o maior não é a raiz, trocar e continuar heapificando if maior != raiz { vetor.swap(raiz, maior); heapify(vetor, tamanho, maior); } } fn main() { let mut numeros = vec![4, 10, 3, 5, 1, 8, 7, 2, 9, 6]; println!("Antes: {:?}", numeros); heap_sort(&mut numeros); println!("Depois: {:?}", numeros); let mut letras = vec!['h', 'e', 'a', 'p', 's', 'o', 'r', 't']; println!("\nAntes: {:?}", letras); heap_sort(&mut letras); println!("Depois: {:?}", letras); } ``` ## Exemplo de Execução ```text Antes: [4, 10, 3, 5, 1, 8, 7, 2, 9, 6] Depois: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] Antes: ['h', 'e', 'a', 'p', 's', 'o', 'r', 't'] Depois: ['a', 'e', 'h', 'o', 'p', 'r', 's', 't'] ``` Versão com rastreamento detalhado do heapify: ```rust fn heap_sort_rastreado(vetor: &mut Vec) { let n = vetor.len(); // Fase 1: Construir max-heap println!("=== Construindo Max-Heap ==="); for i in (0..n / 2).rev() { println!(" heapify(raiz={}={}) em {:?}", i, vetor[i], vetor); heapify_rastreado(vetor, n, i); } println!("Max-Heap: {:?}\n", vetor); // Fase 2: Extrair println!("=== Extraindo Elementos ==="); for fim in (1..n).rev() { println!(" Extrair {} (raiz), trocar com posição {}", vetor[0], fim); vetor.swap(0, fim); heapify_rastreado(vetor, fim, 0); println!(" Estado: {:?} | Ordenado: {:?}", &vetor[..fim], &vetor[fim..]); } } fn heapify_rastreado(vetor: &mut Vec, tamanho: usize, raiz: usize) { let mut maior = raiz; let esq = 2 * raiz + 1; let dir = 2 * raiz + 2; if esq < tamanho && vetor[esq] > vetor[maior] { maior = esq; } if dir < tamanho && vetor[dir] > vetor[maior] { maior = dir; } if maior != raiz { println!(" swap {}({}) ↔ {}({})", raiz, vetor[raiz], maior, vetor[maior]); vetor.swap(raiz, maior); heapify_rastreado(vetor, tamanho, maior); } } fn main() { let mut v = vec![4, 10, 3, 5, 1]; println!("Entrada: {:?}\n", v); heap_sort_rastreado(&mut v); println!("\nResultado: {:?}", v); } ``` ## Variações e Otimizações ### 1. Heapify Iterativo A versão recursiva do heapify pode causar overhead de chamadas de função. A versão iterativa é mais eficiente: ```rust /// Heapify iterativo — evita overhead de recursão. fn heapify_iterativo(vetor: &mut [T], tamanho: usize, mut raiz: usize) { loop { let mut maior = raiz; let esq = 2 * raiz + 1; let dir = 2 * raiz + 2; if esq < tamanho && vetor[esq] > vetor[maior] { maior = esq; } if dir < tamanho && vetor[dir] > vetor[maior] { maior = dir; } if maior == raiz { break; // Propriedade heap satisfeita } vetor.swap(raiz, maior); raiz = maior; // Continuar heapificando na subárvore afetada } } fn heap_sort_iterativo(vetor: &mut [T]) { let n = vetor.len(); if n <= 1 { return; } for i in (0..n / 2).rev() { heapify_iterativo(vetor, n, i); } for fim in (1..n).rev() { vetor.swap(0, fim); heapify_iterativo(vetor, fim, 0); } } fn main() { let mut v = vec![12, 11, 13, 5, 6, 7, 3, 1, 9]; println!("Antes: {:?}", v); heap_sort_iterativo(&mut v); println!("Depois: {:?}", v); } ``` ### 2. Usando BinaryHeap da Biblioteca Padrão O Rust fornece `std::collections::BinaryHeap`, um max-heap pronto para uso: ```rust use std::collections::BinaryHeap; /// Ordenação usando BinaryHeap da biblioteca padrão. /// Simples e eficiente, mas usa O(n) de espaço extra. fn heap_sort_stdlib(vetor: Vec) -> Vec { // Construir o heap a partir do vetor let heap: BinaryHeap = vetor.into_iter().collect(); // into_sorted_vec() retorna em ordem crescente heap.into_sorted_vec() } /// Encontrar os k maiores elementos usando BinaryHeap. fn k_maiores(vetor: &[T], k: usize) -> Vec { let heap: BinaryHeap = vetor.iter().cloned().collect(); heap.into_sorted_vec().into_iter().rev().take(k).collect() } fn main() { let v = vec![4, 10, 3, 5, 1, 8, 7]; println!("Original: {:?}", v); let ordenado = heap_sort_stdlib(v.clone()); println!("Ordenado: {:?}", ordenado); let top3 = k_maiores(&v, 3); println!("Top 3: {:?}", top3); } ``` ### 3. Min-Heap para Ordenação Decrescente Invertendo a comparação, construímos um min-heap para ordenar em ordem decrescente: ```rust /// Heap Sort decrescente usando min-heap. fn heap_sort_decrescente(vetor: &mut [T]) { let n = vetor.len(); if n <= 1 { return; } // Construir min-heap for i in (0..n / 2).rev() { min_heapify(vetor, n, i); } // Extrair o menor para o final (resultado decrescente) for fim in (1..n).rev() { vetor.swap(0, fim); min_heapify(vetor, fim, 0); } } fn min_heapify(vetor: &mut [T], tamanho: usize, mut raiz: usize) { loop { let mut menor = raiz; let esq = 2 * raiz + 1; let dir = 2 * raiz + 2; if esq < tamanho && vetor[esq] < vetor[menor] { menor = esq; } if dir < tamanho && vetor[dir] < vetor[menor] { menor = dir; } if menor == raiz { break; } vetor.swap(raiz, menor); raiz = menor; } } fn main() { let mut v = vec![4, 10, 3, 5, 1, 8, 7]; println!("Antes: {:?}", v); heap_sort_decrescente(&mut v); println!("Decrescente: {:?}", v); } ``` ## Quando Usar O Heap Sort e a escolha adequada nos seguintes cenários: - **Garantia de O(n log n) in-place:** quando você precisa de complexidade O(n log n) garantida E não pode usar memória extra. O Heap Sort é o único algoritmo comum que oferece ambas as propriedades. - **Sistemas de tempo real:** a previsibilidade do tempo de execução (sem pior caso degenerado) é importante em sistemas onde o tempo de resposta máximo é crítico. - **Priority queues:** o heap é a estrutura ideal para filas de prioridade. O `BinaryHeap` do Rust implementa isso nativamente. - **Top-K / Bottom-K:** para encontrar os k maiores ou menores elementos, um heap de tamanho k é mais eficiente que ordenar todo o vetor. - **Streaming de dados:** quando os dados chegam continuamente e você precisa manter os k maiores em tempo real. **Evite** o Heap Sort quando: - Velocidade prática for a prioridade — o [Quick Sort](/algoritmos/quick-sort/) é geralmente 2-3x mais rápido. - Estabilidade for necessária — o Heap Sort é instável. - Dados estiverem parcialmente ordenados — o [Insertion Sort](/algoritmos/insertion-sort/) ou TimSort aproveitam essa situação. ## Comparação com Outros Algoritmos | Característica | Heap Sort | [Quick Sort](/algoritmos/quick-sort/) | [Merge Sort](/algoritmos/merge-sort/) | [Selection Sort](/algoritmos/selection-sort/) | |---|---|---|---|---| | Tempo (médio) | O(n log n) | O(n log n) | O(n log n) | O(n²) | | Tempo (pior) | O(n log n) ✓ | O(n²) | O(n log n) ✓ | O(n²) | | Espaço | O(1) ✓ | O(log n) | O(n) | O(1) ✓ | | Estável | Não | Não | Sim ✓ | Não | | Cache-friendly | Não | Sim ✓ | Razoável | Sim | | In-place | Sim ✓ | Sim ✓ | Não | Sim ✓ | | Adaptativo | Não | Não | Não | Não | O Heap Sort pode ser visto como uma versão melhorada do Selection Sort: em vez de fazer busca linear pelo mínimo a cada passo (O(n)), usa um heap para encontrá-lo em O(log n). Porém, seu padrão de acesso à memória (saltando entre pai e filhos no vetor) causa muitas falhas de cache, tornando-o mais lento que o Quick Sort na prática. ## Exercícios Práticos 1. **K menores com min-heap:** Implemente uma função que encontra os `k` menores elementos de um vetor usando um max-heap de tamanho `k`. A complexidade deve ser O(n log k), melhor que O(n log n) para k pequeno. 2. **Mediana em streaming:** Use dois heaps (um max-heap e um min-heap) para manter a mediana de uma sequência de números que chegam um por vez. A operação de inserção e consulta da mediana deve ser O(log n). 3. **Heap Sort com heapify bottom-up de Floyd:** Implemente a construção do heap usando o método de Floyd (bottom-up) e verifique que é realmente O(n). Conte o número de comparações e confirme que é menor que n * log(n). 4. **Comparação com BinaryHeap:** Implemente o Heap Sort manual e compare com a versão usando `BinaryHeap::into_sorted_vec()` da biblioteca padrão. Meça o tempo para vetores de 100.000 elementos. Qual é mais rápido? Por quê? ## Veja Também - [Quick Sort em Rust](/algoritmos/quick-sort/) — geralmente mais rápido na prática - [Merge Sort em Rust](/algoritmos/merge-sort/) — estável com O(n log n) garantido - [Selection Sort em Rust](/algoritmos/selection-sort/) — versão O(n²) do mesmo conceito - [Vec — Vetores Dinâmicos](/stdlib/vec/) — representação do heap em vetor - [BinaryHeap — Heap Binário](/stdlib/binaryheap/) — implementação da biblioteca padrão - [Slice — Fatias de Memória](/stdlib/slice/) — operações de troca e slicing