---
title: "BinaryHeap\u003cT\u003e: Fila de Prioridade em Rust"
url: "https://rustlang.com.br/stdlib/binaryheap/"
markdown_url: "https://rustlang.com.br/stdlib/binaryheap.MD"
description: "Guia completo do BinaryHeap em Rust: fila de prioridade max-heap, push/pop/peek, min-heap com Reverse, into_sorted_vec e exemplos práticos em português."
date: "2026-02-23"
author: "Equipe Rust Brasil"
---

# BinaryHeap<T>: Fila de Prioridade em Rust

Guia completo do BinaryHeap em Rust: fila de prioridade max-heap, push/pop/peek, min-heap com Reverse, into_sorted_vec e exemplos práticos em português.


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`](/stdlib/btreeset/). Se precisa apenas do máximo de um vetor estático, use `iter().max()`.

## Criando e Inicializando

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

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

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

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

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

```rust
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](/stdlib/btreeset/) --- conjunto com iteração em ordem e range queries
- [BTreeMap: Mapa Ordenado](/stdlib/btreemap/) --- mapa com chaves ordenadas
- [Vec em Rust](/stdlib/vec/) --- vetor dinâmico usado internamente pelo BinaryHeap
- [VecDeque: Fila de Duas Pontas](/stdlib/vecdeque/) --- fila FIFO eficiente
- [Ordenar Vetor em Rust](/receitas/ordenar-vetor/) --- técnicas de ordenação
- [Traits e Generics](/tutoriais/traits-generics/) --- implementando Ord para tipos customizados