VecDeque, HashSet y BinaryHeap: y cómo elegir la colección correcta

Vec, HashMap y BTreeMap cubren la mayoría de los casos, pero la biblioteca estándar guarda tres colecciones más, cada una afilada para un patrón de acceso concreto. VecDeque es una cola eficiente por ambos extremos; HashSet responde solo a “¿está esto aquí?”; BinaryHeap entrega siempre el elemento de mayor prioridad. Conocerlas es media batalla; la otra media es saber elegir. La pregunta que decide la colección correcta no es “¿cuál es la más rápida?”, sino “¿cómo voy a acceder a estos datos?” —por índice, por los extremos, por pertenencia, por orden o por prioridad—.

VecDeque: la cola por ambos extremos

Un Vec es óptimo por el final —push y pop amortizados O(1)— pero pésimo por el principio: insert(0, x) o remove(0) obligan a desplazar todos los demás elementos, en O(n). Cuando necesitas una cola de verdad, que crezca por un extremo y mengüe por el otro, la respuesta es VecDeque<T>: una cola de doble extremo con push_front, push_back, pop_front y pop_back, todos amortizados O(1).

use std::collections::VecDeque;

fn main() {
    let mut cola: VecDeque<i32> = VecDeque::new();
    cola.push_back(1);    // por el final
    cola.push_back(2);
    cola.push_front(0);   // por el principio, sin desplazar nada: O(1)

    assert_eq!(cola.pop_front(), Some(0)); // saca por delante
    assert_eq!(cola[0], 1);                 // indexacion tambien O(1)
    assert_eq!(cola.pop_back(), Some(2));   // ...o por detras
}

El truco está en su representación: un VecDeque es un buffer circular (ring buffer) sobre una única reserva contigua, con dos índices, cabeza y cola, que avanzan y dan la vuelta al llegar al final. Empujar por delante solo mueve el índice de cabeza hacia atrás; no desplaza datos. Por eso conserva casi toda la cache-friendliness de un Vec —sigue siendo una sola asignación contigua— mientras gana el extremo frontal barato. La única cesión es que, al poder envolverse, sus elementos no siempre son un tramo contiguo en memoria: por eso ofrece as_slices, que devuelve dos slices en vez de uno. Es la estructura natural para colas FIFO, ventanas deslizantes y el recorrido en anchura (BFS) de un grafo.

HashSet: pertenencia sin valor

A veces no quieres asociar un valor a una clave, solo saber si un elemento está o no está. Para eso es HashSet<T>, que por dentro es literalmente un HashMap<T, ()>: guarda elementos únicos y responde a contains en tiempo constante medio, con el mismo requisito T: Hash + Eq. Insertar un duplicado no hace nada y insert devuelve false para avisarlo.

use std::collections::HashSet;

fn main() {
    let mut vistos: HashSet<&str> = HashSet::new();
    assert!(vistos.insert("a"));   // true: era nuevo
    assert!(!vistos.insert("a"));  // false: ya estaba, no se duplica
    println!("{}", vistos.contains("a")); // true, en O(1) medio

    // Operaciones de conjunto, directas:
    let a: HashSet<i32> = [1, 2, 3].into_iter().collect();
    let b: HashSet<i32> = [2, 3, 4].into_iter().collect();
    let comun: Vec<_> = a.intersection(&b).collect();      // 2 y 3
    let solo_a: Vec<_> = a.difference(&b).collect();        // 1
    println!("{comun:?} {solo_a:?}");
}

Sus dos usos canónicos son la deduplicación (recoger una secuencia en un HashSet funde repetidos) y la pertenencia rápida —el clásico conjunto de “ya visitados” en algoritmos de grafos, que evita reprocesar nodos—. Además ofrece el álgebra de conjuntos completa: union, intersection, difference, symmetric_difference, is_subset, is_disjoint. Si necesitaras el conjunto ordenado o con consultas de rango, ya sabes que la variante es BTreeSet.

BinaryHeap: la cola de prioridad

Cuando lo que necesitas en cada paso no es un elemento cualquiera sino el más prioritario —el máximo—, la estructura es BinaryHeap<T> con T: Ord. Es un montículo binario implementado sobre un Vec: push y pop cuestan O(log n), y peek —mirar el máximo sin sacarlo— es O(1). No mantiene todo ordenado, solo garantiza que la cima es siempre el mayor.

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

fn main() {
    let mut monticulo = BinaryHeap::new();
    for x in [3, 1, 4, 1, 5, 9, 2] {
        monticulo.push(x);
    }
    assert_eq!(monticulo.peek(), Some(&9));  // la cima es el maximo, O(1)
    assert_eq!(monticulo.pop(), Some(9));    // saca el maximo, O(log n)
    assert_eq!(monticulo.pop(), Some(5));    // luego el siguiente mayor

    // MIN-heap: envuelve en Reverse para invertir el orden.
    let mut minimos = BinaryHeap::new();
    for x in [3, 1, 4, 1, 5] {
        minimos.push(Reverse(x));
    }
    assert_eq!(minimos.pop(), Some(Reverse(1))); // ahora sale el minimo
}

Por defecto es un max-heap: pop entrega el mayor. Para un min-heap no hay tipo aparte; se envuelve cada elemento en std::cmp::Reverse, que invierte el orden y hace que la cima pase a ser el menor —un truco idiomático que reutiliza el mismo montículo—. Es la columna vertebral de las colas de prioridad: planificadores de tareas, el algoritmo de Dijkstra, la fusión de flujos ordenados o quedarte con los k mayores de un torrente. Si al final quieres todo ordenado de una vez, into_sorted_vec lo vacía en un Vec creciente.

Elegir la colección: una guía por acceso

Toda esta variedad se ordena con una sola pregunta: ¿cómo accedes a los datos? El patrón de acceso, no la costumbre, elige la estructura.