Heap Binário | Rust Brasil

Introdução

O Heap Binário é uma árvore binária completa com uma propriedade especial de ordenação: em um max-heap, o valor de cada nó é maior ou igual aos valores de seus filhos; em um min-heap, é menor ou igual. O heap é a estrutura de dados ideal para implementar filas de prioridade, onde sempre precisamos acessar o elemento de maior (ou menor) prioridade de forma eficiente.

A característica mais elegante do heap binário é que ele pode ser representado inteiramente por um array (ou Vec em Rust), sem necessidade de ponteiros. Essa representação compacta oferece excelente localidade de cache e simplicidade de implementação. A biblioteca padrão de Rust fornece BinaryHeap<T>, que é um max-heap pronto para uso em produção.

Conceito e Teoria

Propriedades do Heap

    Max-Heap:                     Min-Heap:
    (pai >= filhos)               (pai <= filhos)

         [90]                        [5]
        /    \                      /   \
      [80]   [70]                [10]   [15]
     /   \   /                  /   \   /
   [50] [60][30]             [20] [30][25]

    Maior no topo ↑              Menor no topo ↑

Propriedade estrutural: O heap é uma árvore binária completa — todos os níveis estão preenchidos, exceto possivelmente o último, que é preenchido da esquerda para a direita.

Representação por Array

A grande sacada do heap binário é que a árvore completa pode ser armazenada em um array sem desperdício de espaço:

    Árvore:           Array (índice 0):
         [90]         [90, 80, 70, 50, 60, 30]
        /    \          0   1   2   3   4   5
      [80]   [70]
     /   \   /
   [50] [60][30]

    Fórmulas de navegação (índice começando em 0):
    ┌─────────────────────────────────────────────┐
    │  Pai de i:           (i - 1) / 2            │
    │  Filho esquerdo de i: 2 * i + 1             │
    │  Filho direito de i:  2 * i + 2             │
    └─────────────────────────────────────────────┘

    Exemplo para o nó [80] (índice 1):
    - Pai: (1-1)/2 = 0 → [90]  ✓
    - Filho esq: 2*1+1 = 3 → [50]  ✓
    - Filho dir: 2*1+2 = 4 → [60]  ✓

Operação: Inserir (sift-up / bubble-up)

Insere no final do array e “sobe” o elemento até a posição correta:

    Inserir 95 no max-heap [90, 80, 70, 50, 60, 30]:

    Passo 1: Adicionar no final
    [90, 80, 70, 50, 60, 30, 95]
                                ^

    Passo 2: 95 > pai(70)? Sim → troca
    [90, 80, 95, 50, 60, 30, 70]
              ^               ^

    Passo 3: 95 > pai(90)? Sim → troca
    [95, 80, 90, 50, 60, 30, 70]
      ^       ^

    Passo 4: Chegou na raiz → parou!

    Resultado:
         [95]
        /    \
      [80]   [90]
     /   \   /  \
   [50] [60][30][70]

Operação: Extrair Máximo (sift-down / bubble-down)

Remove a raiz, coloca o último elemento no topo e “desce” até a posição correta:

    Extrair máximo do max-heap [95, 80, 90, 50, 60, 30, 70]:

    Passo 1: Salvar raiz (95), mover último para raiz
    [70, 80, 90, 50, 60, 30]
      ^

    Passo 2: 70 < maior filho (90)? Sim → troca com 90
    [90, 80, 70, 50, 60, 30]
      ^       ^

    Passo 3: 70 < maior filho (30)? Não → parou!

    Resultado: retorna 95
         [90]
        /    \
      [80]   [70]
     /   \   /
   [50] [60][30]

Heapify: Construir Heap a partir de Array

Em vez de inserir elementos um a um (O(n log n)), podemos construir o heap em O(n) aplicando sift-down de baixo para cima:

    Array desordenado: [30, 50, 90, 10, 80, 70, 60]

    Heapify (max-heap) — processa de trás para frente:
    Índice 2: [30, 50, 90, ...] → 90 OK (filhos são 70, 60)
    Índice 1: [30, 80, 90, 10, 50, ...] → swap 50↔80
    Índice 0: [90, 80, 70, 10, 50, 30, 60] → swap 30↔90, sift down

    Resultado: [90, 80, 70, 10, 50, 30, 60]

Complexidade

Operação	Complexidade
Inserir	O(log n)
Extrair máx/mín	O(log n)
Peek (ver topo)	O(1)
Heapify (construir)	O(n)
Busca arbitrária	O(n)
Espaço	O(n)

Nota: O heap NÃO é eficiente para busca arbitrária (O(n)). Ele é otimizado para acessar e remover o elemento extremo (máximo ou mínimo).

Implementação em Rust

use std::fmt::Display;

/// Heap Binário genérico com suporte a min-heap e max-heap
#[derive(Debug)]
struct HeapBinario<T: Ord + Display> {
    dados: Vec<T>,
    eh_max_heap: bool, // true = max-heap, false = min-heap
}

impl<T: Ord + Display> HeapBinario<T> {
    /// Cria um max-heap vazio
    fn novo_max() -> Self {
        HeapBinario {
            dados: Vec::new(),
            eh_max_heap: true,
        }
    }

    /// Cria um min-heap vazio
    fn novo_min() -> Self {
        HeapBinario {
            dados: Vec::new(),
            eh_max_heap: false,
        }
    }

    /// Retorna o número de elementos
    fn tamanho(&self) -> usize {
        self.dados.len()
    }

    /// Verifica se o heap está vazio
    fn esta_vazio(&self) -> bool {
        self.dados.is_empty()
    }

    /// Retorna referência ao elemento no topo sem remover
    fn peek(&self) -> Option<&T> {
        self.dados.first()
    }

    /// Compara dois elementos respeitando o tipo de heap
    fn deve_subir(&self, filho: &T, pai: &T) -> bool {
        if self.eh_max_heap {
            filho > pai // Max-heap: maior sobe
        } else {
            filho < pai // Min-heap: menor sobe
        }
    }

    /// Índice do pai
    fn pai(i: usize) -> usize {
        (i - 1) / 2
    }

    /// Índice do filho esquerdo
    fn filho_esquerdo(i: usize) -> usize {
        2 * i + 1
    }

    /// Índice do filho direito
    fn filho_direito(i: usize) -> usize {
        2 * i + 2
    }

    /// Insere um elemento no heap
    fn inserir(&mut self, valor: T) {
        self.dados.push(valor);
        self.subir(self.dados.len() - 1);
    }

    /// Sift-up: sobe o elemento na posição i até restaurar a propriedade do heap
    fn subir(&mut self, mut i: usize) {
        while i > 0 {
            let pai = Self::pai(i);
            if self.deve_subir(&self.dados[i], &self.dados[pai]) {
                self.dados.swap(i, pai);
                i = pai;
            } else {
                break;
            }
        }
    }

    /// Extrai o elemento do topo (máximo em max-heap, mínimo em min-heap)
    fn extrair(&mut self) -> Option<T> {
        if self.dados.is_empty() {
            return None;
        }

        let ultimo = self.dados.len() - 1;
        self.dados.swap(0, ultimo);
        let extraido = self.dados.pop();

        if !self.dados.is_empty() {
            self.descer(0);
        }

        extraido
    }

    /// Sift-down: desce o elemento na posição i até restaurar a propriedade do heap
    fn descer(&mut self, mut i: usize) {
        let n = self.dados.len();
        loop {
            let esq = Self::filho_esquerdo(i);
            let dir = Self::filho_direito(i);
            let mut alvo = i;

            // Encontra o filho que deveria estar mais acima
            if esq < n && self.deve_subir(&self.dados[esq], &self.dados[alvo]) {
                alvo = esq;
            }
            if dir < n && self.deve_subir(&self.dados[dir], &self.dados[alvo]) {
                alvo = dir;
            }

            if alvo != i {
                self.dados.swap(i, alvo);
                i = alvo;
            } else {
                break;
            }
        }
    }

    /// Constrói um heap a partir de um vetor existente em O(n)
    fn heapify(dados: Vec<T>, eh_max_heap: bool) -> Self {
        let mut heap = HeapBinario {
            dados,
            eh_max_heap,
        };

        // Aplica sift-down de baixo para cima (ignora folhas)
        let n = heap.dados.len();
        if n > 1 {
            for i in (0..n / 2).rev() {
                heap.descer(i);
            }
        }

        heap
    }

    /// Exibe o heap como árvore (formato visual)
    fn exibir(&self) {
        if self.dados.is_empty() {
            println!("  (vazio)");
            return;
        }
        let tipo = if self.eh_max_heap { "Max-Heap" } else { "Min-Heap" };
        println!("  {} - Array: {:?}",
            tipo,
            self.dados.iter().map(|x| format!("{}", x)).collect::<Vec<_>>()
        );
    }
}

/// Implementação do Heap Sort usando o heap binário
fn heap_sort<T: Ord + Display>(mut dados: Vec<T>) -> Vec<T> {
    let mut heap = HeapBinario::heapify(dados, true); // Max-heap
    let mut ordenado = Vec::with_capacity(heap.tamanho());

    while let Some(max) = heap.extrair() {
        ordenado.push(max);
    }

    ordenado.reverse(); // Inverte para ordem crescente
    ordenado
}

fn main() {
    println!("=== Max-Heap ===");
    let mut max_heap = HeapBinario::novo_max();

    for v in [40, 10, 70, 30, 90, 20, 80, 50, 60] {
        max_heap.inserir(v);
    }
    max_heap.exibir();
    println!("  Topo (máximo): {:?}", max_heap.peek());

    println!("\n  Extraindo em ordem:");
    while let Some(v) = max_heap.extrair() {
        print!("  {} ", v);
    }
    println!();

    println!("\n=== Min-Heap ===");
    let mut min_heap = HeapBinario::novo_min();

    for v in [40, 10, 70, 30, 90, 20, 80, 50, 60] {
        min_heap.inserir(v);
    }
    min_heap.exibir();
    println!("  Topo (mínimo): {:?}", min_heap.peek());

    println!("\n=== Heapify (construção em O(n)) ===");
    let dados = vec![30, 50, 90, 10, 80, 70, 60];
    println!("  Array original: {:?}", dados);
    let heap = HeapBinario::heapify(dados, true);
    heap.exibir();

    println!("\n=== Heap Sort ===");
    let desordenado = vec![64, 25, 12, 22, 11, 90, 45, 33];
    println!("  Entrada: {:?}", desordenado);
    let ordenado = heap_sort(desordenado);
    println!("  Saída:   {:?}", ordenado);
}

Métodos Principais

Método	Descrição
`novo_max()`	Cria um max-heap vazio
`novo_min()`	Cria um min-heap vazio
`inserir(valor)`	Insere e restaura a propriedade com sift-up
`extrair()`	Remove e retorna o elemento do topo
`peek()`	Retorna referência ao topo sem remover
`heapify(vec, tipo)`	Constrói heap a partir de vetor em O(n)
`tamanho()`	Retorna o número de elementos
`esta_vazio()`	Verifica se o heap está vazio
`subir(i)`	Sift-up: restaura propriedade subindo o elemento
`descer(i)`	Sift-down: restaura propriedade descendo o elemento

BinaryHeap na Biblioteca Padrão

use std::collections::BinaryHeap;
use std::cmp::Reverse;

fn main() {
    // Max-heap (padrão)
    let mut max_heap = BinaryHeap::new();
    max_heap.push(30);
    max_heap.push(10);
    max_heap.push(50);
    max_heap.push(20);

    println!("Max-heap - topo: {:?}", max_heap.peek()); // Some(50)

    // Min-heap usando Reverse
    let mut min_heap = BinaryHeap::new();
    min_heap.push(Reverse(30));
    min_heap.push(Reverse(10));
    min_heap.push(Reverse(50));
    min_heap.push(Reverse(20));

    println!("Min-heap - topo: {:?}", min_heap.peek()); // Some(Reverse(10))

    // Extrair em ordem de prioridade
    while let Some(Reverse(v)) = min_heap.pop() {
        print!("{} ", v); // 10 20 30 50
    }
    println!();
}

Exemplo Prático: Simulação de Fila de Tarefas com Prioridade

use std::collections::BinaryHeap;
use std::cmp::Ordering;

/// Tarefa com prioridade e prazo
#[derive(Debug, Clone, Eq, PartialEq)]
struct Tarefa {
    nome: String,
    prioridade: u8,    // 1 = baixa, 5 = crítica
    prazo_minutos: u32, // Prazo em minutos
}

impl Tarefa {
    fn nova(nome: &str, prioridade: u8, prazo: u32) -> Self {
        Tarefa {
            nome: nome.to_string(),
            prioridade,
            prazo_minutos: prazo,
        }
    }

    fn descricao_prioridade(&self) -> &str {
        match self.prioridade {
            1 => "Baixa",
            2 => "Normal",
            3 => "Alta",
            4 => "Urgente",
            5 => "Crítica",
            _ => "Desconhecida",
        }
    }
}

/// Ordenação: maior prioridade primeiro; em caso de empate, menor prazo primeiro
impl Ord for Tarefa {
    fn cmp(&self, other: &Self) -> Ordering {
        self.prioridade
            .cmp(&other.prioridade)
            .then_with(|| other.prazo_minutos.cmp(&self.prazo_minutos))
    }
}

impl PartialOrd for Tarefa {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

fn main() {
    let mut fila = BinaryHeap::new();

    // Adicionar tarefas com diferentes prioridades
    fila.push(Tarefa::nova("Corrigir bug em produção", 5, 30));
    fila.push(Tarefa::nova("Atualizar documentação", 1, 480));
    fila.push(Tarefa::nova("Implementar nova feature", 3, 240));
    fila.push(Tarefa::nova("Revisar pull request", 3, 60));
    fila.push(Tarefa::nova("Deploy para staging", 4, 120));
    fila.push(Tarefa::nova("Responder e-mails", 2, 360));
    fila.push(Tarefa::nova("Reunião com cliente", 4, 45));

    println!("=== Fila de Tarefas (ordem de execução) ===\n");
    println!("{:<35} {:>10} {:>15}", "Tarefa", "Prioridade", "Prazo (min)");
    println!("{}", "-".repeat(62));

    let mut tempo_total = 0u32;
    while let Some(tarefa) = fila.pop() {
        tempo_total += tarefa.prazo_minutos;
        println!(
            "{:<35} {:>10} {:>15}",
            tarefa.nome,
            tarefa.descricao_prioridade(),
            tarefa.prazo_minutos
        );
    }

    println!("{}", "-".repeat(62));
    println!(
        "Tempo total estimado: {} horas e {} minutos",
        tempo_total / 60,
        tempo_total % 60
    );
}

Comparação com Outras Estruturas

Critério	Heap Binário	Lista Ordenada	BST Balanceada	Array Desordenado
Inserir	O(log n)	O(n)	O(log n)	O(1)
Extrair extremo	O(log n)	O(1)	O(log n)	O(n)
Peek (ver extremo)	O(1)	O(1)	O(log n)	O(n)
Busca arbitrária	O(n)	O(n)	O(log n)	O(n)
Construção (heapify)	O(n)	O(n log n)	O(n log n)	O(1)
Uso de memória	Compacto	Ponteiros	Ponteiros	Compacto
Cache-friendly	Sim	Não	Não	Sim

Quando usar Heap Binário?

Use quando precisa de acesso rápido ao maior ou menor elemento.
Use para filas de prioridade (agendadores, simulações, algoritmos de grafos como Dijkstra).
Use para o algoritmo Heap Sort (ordenação in-place O(n log n)).
Não use se precisa buscar elementos arbitrários — use BST ou HashMap.
Não use se precisa de dados totalmente ordenados — use BTreeSet ou Vec ordenado.

Exercícios

Exercício 1: Mediana Contínua

Implemente uma estrutura que mantém dois heaps (um max-heap e um min-heap) para calcular a mediana de um fluxo contínuo de números. O max-heap guarda a metade inferior e o min-heap guarda a metade superior. A mediana é obtida em O(1) e cada inserção custa O(log n).

Exercício 2: K Maiores Elementos

Dada uma lista de n números, encontre os k maiores elementos usando um min-heap de tamanho k. Isso é mais eficiente que ordenar toda a lista quando k « n. Implemente e compare o desempenho com a abordagem de ordenação completa.

Exercício 3: Merge de K Listas Ordenadas

Dadas k listas ordenadas, combine-as em uma única lista ordenada usando um min-heap. Cada elemento do heap deve conter o valor e o índice da lista de origem. A complexidade deve ser O(n * log k), onde n é o total de elementos.

Entrada:
  Lista 1: [1, 4, 7]
  Lista 2: [2, 5, 8]
  Lista 3: [3, 6, 9]

Saída: [1, 2, 3, 4, 5, 6, 7, 8, 9]

Conclusão

O heap binário é uma estrutura de dados surpreendentemente simples e poderosa. Sua representação por array elimina a necessidade de ponteiros e oferece excelente localidade de cache, enquanto as operações de sift-up e sift-down mantêm a propriedade de ordenação parcial com eficiência O(log n).

Em Rust, o BinaryHeap da biblioteca padrão é a escolha ideal para filas de prioridade em produção. Para min-heaps, o wrapper Reverse oferece uma solução idiomática e sem custo de performance. Compreender o heap binário é fundamental, pois ele aparece como componente em diversos algoritmos clássicos: Dijkstra para caminhos mínimos, Prim para árvore geradora mínima, Huffman para compressão, e o próprio Heap Sort para ordenação.