VecDeque, BinaryHeap & LinkedList

VecDeque é uma fila de duas pontas. BinaryHeap é uma fila de prioridade (max-heap). LinkedList raramente é a escolha certa em Rust.

Receita

use std::collections::{BinaryHeap, VecDeque};
 
fn main() {
    let mut q = VecDeque::from([1, 2]);
    q.push_front(0);
 
    let mut heap = BinaryHeap::from([1, 3, 2]);
    assert_eq!(heap.pop(), Some(3));
}

Quando usar isto: Filas BFS, escalonadores, problemas de top-K - evite LinkedList a menos que tenha necessidade medida.

Exemplo de Trabalho

use std::collections::BinaryHeap;
 
#[derive(Eq, PartialEq)]
struct Task { priority: u8, name: &'static str }
impl Ord for Task {
    fn cmp(&self, o: &Self) -> std::cmp::Ordering {
        self.priority.cmp(&o.priority)
    }
}
impl PartialOrd for Task { fn partial_cmp(&self, o: &Self) -> Option<std::cmp::Ordering> { Some(self.cmp(o)) } }
 
fn main() {
    let mut h = BinaryHeap::new();
    h.push(Task { priority: 1, name: "low" });
    h.push(Task { priority: 10, name: "high" });
    println!("{}", h.pop().unwrap().name);
}

O que isto demonstra:

Ord customizado para ordenação de heap
Max-heap remove o de maior prioridade primeiro
VecDeque para FIFO com operações de frente/trás

Análise Profunda

LinkedList aloca por nó - localidade de cache ruim. Prefira Vec ou VecDeque a menos que uma lista intrusiva seja necessária.

BinaryHeap::peek lê o máximo sem remover. VecDeque::make_contiguous para acesso a slice.

Armadilhas

LinkedList por padrão - Mais lento que VecDeque. Correção: Faça benchmark antes de usar.
Min-heap - Inverta Ord ou use std::cmp::Reverse.
Heap com chaves iguais - A ordem não é estável. Correção: Campo de desempate em Ord.
Crescimento do buffer circular do VecDeque - Ainda eficiente em média.
Remover de heap vazia - Retorna None.

Alternativas

Alternativa	Use Quando	Não Use Quando
`Vec` + sort	Pequeno top-K	Streaming de K grande
crate `priority-queue`	Funcionalidades extras	Std é suficiente
deque `crossbeam`	Work-stealing	Fila simples

FAQs

VecDeque vs Vec?

Pop na frente O(1) amortizado para deque.

heap peek_mut?

Ajusta o elemento do topo.

LinkedList splice?

Splice de lista O(1) - uso nicho.

BTreeMap para top-K?

Possível, mas heap é melhor.

serde deque?

Formato Seq.

no_std?

Coleções de alocação onde disponíveis.

fila sync?

crossbeam/mpmc, não BinaryHeap.

prioridade estável?

Contador de desempate em Ord.

capacidade deque?

with_capacity reduz o crescimento.

profile linkedlist?

Quase sempre perde para VecDeque.

Relacionados

Versões do Stack: Esta página foi escrita para Rust 1.97.0 (edição 2024), Tokio 1.x, Axum 0.8, serde 1.0, sqlx 0.8, clap 4, e Polars 0.46+.

VecDeque, BinaryHeap & LinkedList

VecDeque é uma fila de duas pontas. BinaryHeap é uma fila de prioridade (max-heap). LinkedList raramente é a escolha certa em Rust.

Receita

use std::collections::{BinaryHeap, VecDeque};
 
fn main() {
    let mut q = VecDeque::from([1, 2]);
    q.push_front(0);
 
    let mut heap = BinaryHeap::from([1, 3, 2]);
    assert_eq!(heap.pop(), Some(3));
}

Quando usar isto: Filas BFS, escalonadores, problemas de top-K - evite LinkedList a menos que tenha necessidade medida.

Exemplo de Trabalho

use std::collections::BinaryHeap;
 
#[derive(Eq, PartialEq)]
struct Task { priority: u8, name: &'static str }
impl Ord for Task {
    fn cmp(&self, o: &Self) -> std::cmp::Ordering {
        self.priority.cmp(&o.priority)
    }
}
impl PartialOrd for Task { fn partial_cmp(&self, o: &Self) -> Option<std::cmp::Ordering> { Some(self.cmp(o)) } }
 
fn main() {
    let mut h = BinaryHeap::new();
    h.push(Task { priority: 1, name: "low" });
    h.push(Task { priority: 10, name: "high" });
    println!("{}", h.pop().unwrap().name);
}

O que isto demonstra:

Ord customizado para ordenação de heap
Max-heap remove o de maior prioridade primeiro
VecDeque para FIFO com operações de frente/trás

Análise Profunda

LinkedList aloca por nó - localidade de cache ruim. Prefira Vec ou VecDeque a menos que uma lista intrusiva seja necessária.

BinaryHeap::peek lê o máximo sem remover. VecDeque::make_contiguous para acesso a slice.

Armadilhas

LinkedList por padrão - Mais lento que VecDeque. Correção: Faça benchmark antes de usar.
Min-heap - Inverta Ord ou use std::cmp::Reverse.
Heap com chaves iguais - A ordem não é estável. Correção: Campo de desempate em Ord.
Crescimento do buffer circular do VecDeque - Ainda eficiente em média.
Remover de heap vazia - Retorna None.

Alternativas

Alternativa	Use Quando	Não Use Quando
`Vec` + sort	Pequeno top-K	Streaming de K grande
crate `priority-queue`	Funcionalidades extras	Std é suficiente
deque `crossbeam`	Work-stealing	Fila simples

FAQs

VecDeque vs Vec?

Pop na frente O(1) amortizado para deque.

heap peek_mut?

Ajusta o elemento do topo.

LinkedList splice?

Splice de lista O(1) - uso nicho.

BTreeMap para top-K?

Possível, mas heap é melhor.

serde deque?

Formato Seq.

no_std?

Coleções de alocação onde disponíveis.

fila sync?

crossbeam/mpmc, não BinaryHeap.

prioridade estável?

Contador de desempate em Ord.

capacidade deque?

with_capacity reduz o crescimento.

profile linkedlist?

Quase sempre perde para VecDeque.

Relacionados

Versões do Stack: Esta página foi escrita para Rust 1.97.0 (edição 2024), Tokio 1.x, Axum 0.8, serde 1.0, sqlx 0.8, clap 4, e Polars 0.46+.

VecDeque, BinaryHeap & LinkedList

Buscar na documentação

VecDeque, BinaryHeap & LinkedList