---
title: "Heap Binário"
url: "https://rustlang.com.br/estruturas-dados/heap-binario/"
markdown_url: "https://rustlang.com.br/estruturas-dados/heap-binario.MD"
description: "Implemente um Heap Binário em Rust com min-heap e max-heap, representação por array, heapify, insert e extract. Conheça BinaryHeap da stdlib e aplique em simulações de eventos."
date: ""
author: "Equipe Rust Brasil"
---

# Heap Binário

Implemente um Heap Binário em Rust com min-heap e max-heap, representação por array, heapify, insert e extract. Conheça BinaryHeap da stdlib e aplique em simulações de eventos.


## 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

```text
    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:

```text
    Á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:

```text
    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:

```text
    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:

```text
    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

```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

```rust
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

```rust
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.

```text
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.