BinaryHeap<T>: Fila de Prioridade em Rust

O BinaryHeap<T> é a implementação de fila de prioridade (priority queue) da biblioteca padrão do Rust. Ele é um max-heap por padrão, ou seja, o maior elemento está sempre acessível no topo em O(1). Inserção e remoção do topo são realizadas em O(log n). Internamente, usa um vetor (Vec<T>) organizado como uma árvore binária heap.

Quando Usar BinaryHeap

Use BinaryHeap quando:

Precisa acessar repetidamente o maior (ou menor) elemento de uma coleção dinâmica.
Está implementando algoritmos como Dijkstra, Prim, ou qualquer algoritmo que usa fila de prioridade.
Precisa processar tarefas por prioridade.
Quer uma alternativa mais eficiente a ordenar repetidamente um vetor.

Se precisa de todos os elementos ordenados e acessíveis, use BTreeSet. Se precisa apenas do máximo de um vetor estático, use iter().max().

Criando e Inicializando

use std::collections::BinaryHeap;

fn main() {
    // Criar vazio
    let mut heap: BinaryHeap<i32> = BinaryHeap::new();

    // Criar com capacidade
    let mut heap2: BinaryHeap<String> = BinaryHeap::with_capacity(100);

    // Criar a partir de um vetor
    let dados = vec![3, 1, 4, 1, 5, 9, 2, 6];
    let heap3: BinaryHeap<i32> = BinaryHeap::from(dados);

    // Criar a partir de um iterador
    let heap4: BinaryHeap<i32> = (1..=10).collect();

    // O topo é sempre o maior elemento
    println!("Topo: {:?}", heap3.peek()); // Some(9)
    println!("Tamanho: {}", heap3.len()); // 8
}

Tabela de Métodos Comuns

Método	Descrição	Complexidade
`push(value)`	Insere elemento	O(log n)
`pop()`	Remove e retorna o maior; `Option<T>`	O(log n)
`peek()`	Referência ao maior, sem remover	O(1)
`peek_mut()`	Referência mutável ao maior	O(1)*
`len()` / `is_empty()`	Tamanho e verificação	O(1)
`into_sorted_vec()`	Consome o heap e retorna `Vec` ordenado crescente	O(n log n)
`into_vec()`	Consome o heap e retorna `Vec` (não ordenado)	O(1)
`append(&mut other)`	Move todos de `other` para `self`	O(n + m)
`drain()`	Remove todos e retorna iterador (sem ordem)	O(n)
`retain(f)`	Mantém elementos onde `f` retorna `true`	O(n)
`iter()`	Iterador sobre referências (sem ordem garantida!)	O(n)
`capacity()`	Capacidade alocada	O(1)
`reserve(n)`	Reserva espaço para mais `n` elementos	O(n)

* O peek_mut() corrige a posição do elemento no heap quando o PeekMut é descartado (drop).

Exemplos Práticos

1. Max-Heap Básico — Push, Pop e Peek

use std::collections::BinaryHeap;

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

    heap.push(10);
    heap.push(30);
    heap.push(20);
    heap.push(50);
    heap.push(40);

    // peek: ver o maior sem remover
    println!("Maior: {:?}", heap.peek()); // Some(50)

    // pop: remover em ordem decrescente
    println!("\nElementos em ordem de prioridade:");
    while let Some(valor) = heap.pop() {
        println!("  {}", valor);
    }
    // 50, 40, 30, 20, 10

    println!("Heap vazio? {}", heap.is_empty()); // true
}

2. Min-Heap com std::cmp::Reverse

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

fn main() {
    // Reverse inverte a ordenação: o MENOR fica no topo
    let mut min_heap: BinaryHeap<Reverse<i32>> = BinaryHeap::new();

    min_heap.push(Reverse(30));
    min_heap.push(Reverse(10));
    min_heap.push(Reverse(50));
    min_heap.push(Reverse(20));
    min_heap.push(Reverse(40));

    // O menor está no topo
    println!("Menor: {:?}", min_heap.peek()); // Some(Reverse(10))

    // Extrair em ordem crescente
    println!("\nOrdem crescente:");
    while let Some(Reverse(valor)) = min_heap.pop() {
        println!("  {}", valor);
    }
    // 10, 20, 30, 40, 50
}

3. Fila de Prioridade com Structs Customizadas

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

#[derive(Debug, Eq, PartialEq)]
struct Tarefa {
    prioridade: u8,
    descricao: String,
}

// Ordenar por prioridade (maior = mais importante)
impl Ord for Tarefa {
    fn cmp(&self, other: &Self) -> Ordering {
        self.prioridade.cmp(&other.prioridade)
    }
}

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

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

    fila.push(Tarefa {
        prioridade: 2,
        descricao: "Revisar pull request".to_string(),
    });
    fila.push(Tarefa {
        prioridade: 5,
        descricao: "Corrigir bug crítico".to_string(),
    });
    fila.push(Tarefa {
        prioridade: 1,
        descricao: "Atualizar documentação".to_string(),
    });
    fila.push(Tarefa {
        prioridade: 4,
        descricao: "Deploy em staging".to_string(),
    });
    fila.push(Tarefa {
        prioridade: 3,
        descricao: "Escrever testes".to_string(),
    });

    println!("Processando tarefas por prioridade:");
    while let Some(tarefa) = fila.pop() {
        println!("  [P{}] {}", tarefa.prioridade, tarefa.descricao);
    }
    // [P5] Corrigir bug crítico
    // [P4] Deploy em staging
    // [P3] Escrever testes
    // [P2] Revisar pull request
    // [P1] Atualizar documentação
}

4. Algoritmo dos K Maiores Elementos

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

fn k_maiores(dados: &[i32], k: usize) -> Vec<i32> {
    // Usar min-heap de tamanho k para encontrar os k maiores
    let mut min_heap: BinaryHeap<Reverse<i32>> = BinaryHeap::with_capacity(k + 1);

    for &valor in dados {
        min_heap.push(Reverse(valor));
        if min_heap.len() > k {
            min_heap.pop(); // remove o menor
        }
    }

    // Extrair e ordenar (decrescente)
    let mut resultado: Vec<i32> = min_heap.into_iter().map(|Reverse(v)| v).collect();
    resultado.sort_unstable_by(|a, b| b.cmp(a));
    resultado
}

fn main() {
    let dados = vec![38, 27, 43, 3, 9, 82, 10, 56, 71, 4];

    let top3 = k_maiores(&dados, 3);
    println!("Top 3 maiores: {:?}", top3); // [82, 71, 56]

    let top5 = k_maiores(&dados, 5);
    println!("Top 5 maiores: {:?}", top5); // [82, 71, 56, 43, 38]
}

5. into_sorted_vec e Conversões

use std::collections::BinaryHeap;

fn main() {
    let dados = vec![5, 3, 8, 1, 9, 2, 7, 4, 6];
    let heap: BinaryHeap<i32> = BinaryHeap::from(dados);

    // CUIDADO: iter() NÃO garante ordem!
    println!("iter() (sem ordem garantida):");
    for v in heap.iter() {
        print!("{} ", v);
    }
    println!();

    // into_sorted_vec: consome o heap e retorna vetor ordenado
    let ordenado = heap.into_sorted_vec();
    println!("into_sorted_vec: {:?}", ordenado);
    // [1, 2, 3, 4, 5, 6, 7, 8, 9]

    // Heapsort manual
    let mut heap2 = BinaryHeap::from(vec![5, 3, 8, 1, 9]);
    let mut decrescente = Vec::with_capacity(heap2.len());
    while let Some(v) = heap2.pop() {
        decrescente.push(v);
    }
    println!("Decrescente: {:?}", decrescente); // [9, 8, 5, 3, 1]

    // Converter Vec -> BinaryHeap é O(n) (heapify)
    let vec_original = vec![10, 20, 30, 40, 50];
    let heap3 = BinaryHeap::from(vec_original); // O(n), não O(n log n)!

    // Converter BinaryHeap -> Vec é O(1) (sem reordenar)
    let vec_desordenado: Vec<i32> = heap3.into_vec();
    println!("into_vec (não ordenado): {:?}", vec_desordenado);
}

Características de Desempenho

Operação	Complexidade
`push`	O(log n)
`pop`	O(log n)
`peek`	O(1)
`BinaryHeap::from(vec)` (heapify)	O(n)
`into_sorted_vec`	O(n log n)
`into_vec`	O(1)
`append`	O(n + m)
`len` / `is_empty`	O(1)
`iter` (sem ordem)	O(n)

Memória: O BinaryHeap usa um Vec<T> internamente, então tem a mesma eficiência de memória de um vetor — sem overhead de ponteiros como em árvores. A conversão BinaryHeap::from(vec) reutiliza a alocação existente.

BinaryHeap vs Outras Estruturas para Prioridade

Critério	BinaryHeap	BTreeSet	Vec ordenado
Acessar máximo	O(1)	O(log n)	O(1) (último)
Inserir	O(log n)	O(log n)	O(n)
Remover máximo	O(log n)	O(log n)	O(1) (pop)
Remover mínimo	O(n)*	O(log n)	O(n)
Busca por valor	O(n)	O(log n)	O(log n)
Elementos duplicados	Sim	Não	Sim
Iteração ordenada	Não**	Sim	Sim

* Para remover o mínimo do BinaryHeap, use Reverse para criar um min-heap.

** O iter() do BinaryHeap não garante ordem. Use into_sorted_vec() ou faça pop() repetido.

Regra prática: Use BinaryHeap quando precisa repetidamente do maior (ou menor) elemento. Use BTreeSet quando precisa de acesso ordenado a todos os elementos. Use Vec ordenado quando as inserções são raras e as buscas são frequentes.

Veja Também

BTreeSet: Conjunto Ordenado — conjunto com iteração em ordem e range queries
BTreeMap: Mapa Ordenado — mapa com chaves ordenadas
Vec em Rust — vetor dinâmico usado internamente pelo BinaryHeap
VecDeque: Fila de Duas Pontas — fila FIFO eficiente
Ordenar Vetor em Rust — técnicas de ordenação
Traits e Generics — implementando Ord para tipos customizados