Heap Sort em Rust | Rust Brasil

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

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

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

/// Heap Sort genérico.
/// Ordena o slice in-place em ordem crescente usando um max-heap.
fn heap_sort<T: PartialOrd>(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<T: PartialOrd>(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

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:

fn heap_sort_rastreado(vetor: &mut Vec<i32>) {
    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<i32>, 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:

/// Heapify iterativo — evita overhead de recursão.
fn heapify_iterativo<T: PartialOrd>(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<T: PartialOrd>(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:

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<T: Ord>(vetor: Vec<T>) -> Vec<T> {
    // Construir o heap a partir do vetor
    let heap: BinaryHeap<T> = 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<T: Ord + Clone>(vetor: &[T], k: usize) -> Vec<T> {
    let heap: BinaryHeap<T> = 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:

/// Heap Sort decrescente usando min-heap.
fn heap_sort_decrescente<T: PartialOrd>(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<T: PartialOrd>(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 é geralmente 2-3x mais rápido.
Estabilidade for necessária — o Heap Sort é instável.
Dados estiverem parcialmente ordenados — o Insertion Sort ou TimSort aproveitam essa situação.

Comparação com Outros Algoritmos

Característica	Heap Sort	Quick Sort	Merge Sort	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

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.
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).
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).
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 — geralmente mais rápido na prática
Merge Sort em Rust — estável com O(n log n) garantido
Selection Sort em Rust — versão O(n²) do mesmo conceito
Vec — Vetores Dinâmicos — representação do heap em vetor
BinaryHeap — Heap Binário — implementação da biblioteca padrão
Slice — Fatias de Memória — operações de troca e slicing