More Collections: VecDeque, BTreeMap & BinaryHeap

Reviewed & published by Brayan K

Beyond Vec and HashMap, Rust's standard library ships specialized collections — a double-ended queue, an ordered map and set, and a priority heap — each tuned for a job those two cannot do efficiently.

Part of the free Rust course at LearnCodingFast — hands-on lessons with worked examples and the output they print, plus practice exercises and a quick quiz.

In this lesson you'll learn when to reach for VecDeque, BTreeMap, BinaryHeap, and the set types — and why picking the right container makes your code both faster and clearer.

What You'll Learn in This Lesson

• Push and pop from both ends with VecDeque
• Keep keys sorted and do range queries with BTreeMap
• Pull the largest item first with BinaryHeap
• Turn a max-heap into a min-heap using Reverse
• Store unique values with HashSet and BTreeSet
• Choose the right collection over Vec or HashMap

1️⃣ VecDeque — A Double-Ended Queue

A VecDeque<T> is a growable ring buffer that supports fast insertion and removal at both ends. With a plain Vec, removing from the front is O(n) because every other element must shift; VecDeque makes push_front, pop_front, push_back, and pop_back all O(1). The pop methods return Option<T> because the deque might be empty.

use std::collections::VecDeque;

fn main() {
    // A VecDeque is a double-ended queue: fast push/pop at BOTH ends.
    let mut dq: VecDeque<i32> = VecDeque::new();

    dq.push_back(1);    // add to the back  -> [1]
    dq.push_back(2);    //                  -> [1, 2]
    dq.push_front(0);   // add to the front -> [0, 1, 2]

    println!("queue: {:?}", dq);            // -> [0, 1, 2]

    // Pop returns Option, since the deque might be empty.
    let front = dq.pop_front();             // removes 0
    let back = dq.pop_back();               // removes 2
    println!("popped front={:?} back={:?}", front, back);
    println!("remaining: {:?}", dq);        // -> [1]

    // It still indexes like a Vec and reports its length.
    dq.push_back(9);
    println!("len = {}, first = {:?}", dq.len(), dq.front());
}

This is the collection of choice for a FIFO queue: push_back to enqueue and pop_front to dequeue. It is also ideal for breadth-first search and sliding-window algorithms.

2️⃣ BTreeMap & BTreeSet — Always Sorted

A BTreeMap<K, V> stores its entries in a balanced search tree, so iteration always visits keys in sorted order and lookups are O(log n). Unlike a HashMap, it supports range(..) queries and cheap access to the smallest and largest key. The set version, BTreeSet, is the same idea for unique values.

use std::collections::BTreeMap;

fn main() {
    // A BTreeMap keeps its keys in SORTED order (unlike HashMap).
    let mut scores: BTreeMap<&str, i32> = BTreeMap::new();
    scores.insert("Charlie", 70);
    scores.insert("Alice", 95);
    scores.insert("Bob", 82);
    scores.insert("Dave", 60);

    // Iterating always yields keys in ascending order — no sorting needed.
    for (name, score) in &scores {
        println!("{}: {}", name, score);
    }

    // range() gives an ordered slice of keys between two bounds.
    println!("--- names from B up to (not incl.) D ---");
    for (name, score) in scores.range("B".."D") {
        println!("{}: {}", name, score);
    }

    // first/last key-value come for free because it is ordered.
    println!("lowest key:  {:?}", scores.iter().next());
    println!("highest key: {:?}", scores.iter().next_back());
}

The range("B".."D") call returns only the entries whose keys fall in that half-open interval, already in order — something a HashMap simply cannot do without sorting everything first.

3️⃣ BinaryHeap — A Priority Queue

A BinaryHeap<T> is a priority queue: push is O(log n), and pop always removes the largest element (by Ord). To make it a min-heap, wrap each value in std::cmp::Reverse, which flips the comparison so the smallest value comes out first.

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

fn main() {
    // A BinaryHeap is a MAX-heap: pop() always returns the LARGEST item.
    let mut heap = BinaryHeap::new();
    for n in [3, 1, 4, 1, 5, 9, 2].iter() {
        heap.push(*n);
    }

    // peek() looks at the max without removing it.
    println!("max is {:?}", heap.peek());   // -> Some(9)

    // Popping repeatedly drains the heap largest-first.
    print!("largest-first:");
    while let Some(top) = heap.pop() {
        print!(" {}", top);
    }
    println!();

    // Wrap values in Reverse to turn it into a MIN-heap.
    let mut min_heap = BinaryHeap::new();
    for n in [3, 1, 4, 1, 5, 9, 2].iter() {
        min_heap.push(Reverse(*n));
    }
    print!("smallest-first:");
    while let Some(Reverse(top)) = min_heap.pop() {
        print!(" {}", top);
    }
    println!();
}

Heaps shine in algorithms like Dijkstra's shortest path and "top-K" problems, where you repeatedly want the current best (or worst) item without keeping the whole collection sorted.

Sets round out the picture. A HashSet gives fast, unordered uniqueness and set algebra; a BTreeSet keeps the same unique values in sorted order.

use std::collections::{HashSet, BTreeSet};

fn main() {
    // A HashSet stores UNIQUE values with fast membership tests (unordered).
    let mut seen: HashSet<&str> = HashSet::new();
    for word in ["red", "green", "red", "blue", "green"] {
        seen.insert(word);     // duplicates are ignored
    }
    println!("unique count = {}", seen.len());        // -> 3
    println!("contains blue? {}", seen.contains("blue"));

    // Set algebra: intersection, union, difference.
    let a: HashSet<i32> = [1, 2, 3, 4].iter().copied().collect();
    let b: HashSet<i32> = [3, 4, 5, 6].iter().copied().collect();

    let mut both: Vec<i32> = a.intersection(&b).copied().collect();
    both.sort();                                       // HashSet order is random
    println!("in both: {:?}", both);                   // -> [3, 4]

    // A BTreeSet keeps elements SORTED, so iteration is ordered for free.
    let ordered: BTreeSet<i32> = [5, 1, 4, 1, 3].iter().copied().collect();
    println!("sorted unique: {:?}", ordered);          // -> {1, 3, 4, 5}
}

Your turn. Fill in the blanks marked ___, then run it.

// 🎯 YOUR TURN — complete the deque operations, then run it.
use std::collections::VecDeque;

fn main() {
    let mut dq: VecDeque<&str> = VecDeque::new();
    dq.push_back("b");

    // 1) Put "a" at the FRONT so the order becomes a, b.
    dq.___("a");                 // 👉 the push-to-front method

    dq.push_back("c");           // order is now a, b, c

    // 2) Remove and capture the FRONT element.
    let first = dq.___();        // 👉 the pop-from-front method

    println!("first out = {:?}", first);
    println!("now: {:?}", dq);
}

// ✅ Expected output:
//    first out = Some("a")
//    now: ["b", "c"]

Mini-Challenge: Top-3 Smallest

Use a BinaryHeap plus Reverse to pull the three smallest numbers out of a list. Run it with cargo run and check the output.

// 🎯 MINI-CHALLENGE: find the 3 smallest numbers.
//
// 1. Start from let nums = [7, 2, 9, 4, 1, 5];
// 2. Build a BinaryHeap, but push Reverse(n) so it behaves as a MIN-heap.
//    (use std::cmp::Reverse;)
// 3. Pop three times, unwrapping each Reverse(v), and collect the values.
// 4. Print the three smallest values.
//
// ✅ Example output:
//    3 smallest: [1, 2, 4]

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

fn main() {
    // your code here
}

Common Errors (and the fix)

• ❌ Expecting pop() to return the value directly. ✅ All these pops return an Option — match on it or use if let Some(x) = ....
• ❌ Assuming BinaryHeap pops smallest-first. ✅ It is a max-heap; wrap values in std::cmp::Reverse for a min-heap.
• ❌ Relying on HashSet/HashMap iteration order. ✅ It is unspecified and can change run to run; use the BTree variants when you need order.
• ❌ Putting a non-Ord type in a BTreeMap key or BinaryHeap. ✅ Keys and heap items must implement Ord (e.g. f64 does not, by design).

Pro Tips

• 💡 Default to Vec and HashMap — only switch when you need front operations, ordering, or priority.
• 💡 VecDeque is your queue: push_back + pop_front gives a clean FIFO.
• 💡 Need top-K? A BinaryHeap beats sorting the whole list when K is small.

📋 Quick Reference — Choosing a Collection

🎉 Lesson Complete!

• ✅ VecDeque gives O(1) push/pop at both ends
• ✅ BTreeMap/BTreeSet keep keys sorted and support range queries
• ✅ BinaryHeap is a max-heap; Reverse turns it into a min-heap
• ✅ HashSet is fast and unordered; BTreeSet is sorted

Practice quiz

Continue this course

• Previous: Checkpoint: Traits & Generics
• Next: Declarative Macros (macro_rules!) — Write your own macros with matchers, repetition, and hygiene
• Quick reference: Rust cheat sheet

Frequently asked questions

When should I use a VecDeque instead of a Vec?

Reach for VecDeque when you need to add or remove items from the FRONT of a sequence efficiently, not just the back. A Vec gives O(1) push and pop at the end, but removing from the front is O(n) because every other element has to shift down. VecDeque is a ring buffer, so push_front, pop_front, push_back, and pop_back are all O(1). It is the natural choice for queues (FIFO), sliding windows, and breadth-first search. If you only ever touch the end, a plain Vec is simpler and slightly faster.

What is the difference between HashMap and BTreeMap?

Both map keys to values, but they make different trade-offs. HashMap uses hashing for average O(1) lookups and stores entries in an arbitrary, unpredictable order. BTreeMap stores entries in a balanced tree, so lookups are O(log n) but the keys are always kept in sorted order. Choose BTreeMap when you need ordered iteration, range queries (everything between two keys), or the smallest and largest key. Choose HashMap when you just need the fastest possible key-value lookups and order does not matter.

How do I make a BinaryHeap behave as a min-heap?

Rust's BinaryHeap is always a max-heap: pop() and peek() return the largest element according to the Ord ordering. To get a min-heap, wrap each value in std::cmp::Reverse before pushing it. Reverse flips the comparison, so the smallest underlying value compares as the largest wrapped value and therefore comes out first. When you pop, destructure the Reverse(v) to recover the real value. This is the idiomatic standard-library way; you do not need an external crate.

When would I pick a HashSet over a BTreeSet?

Use a HashSet when you only need fast membership tests and uniqueness, and you do not care about order — for example, deduplicating items or tracking which things you have already seen. Use a BTreeSet when you also want the elements kept in sorted order, or you need range queries and ordered iteration. The relationship mirrors HashMap versus BTreeMap: hashing gives average O(1) operations with no order, while the B-tree gives O(log n) operations with guaranteed sorted iteration.