Rust VecDeque & BinaryHeap

Think about the line at a coffee shop. New people join at the back, and the barista serves whoever is at the front. Now think about a hospital waiting room. There, the most urgent patient goes first, no matter when they arrived. Both are “waiting lines”, but they follow different rules.

Rust has a collection for each one. A VecDeque is a fast line where you can add and remove at both ends. A BinaryHeap is a priority queue: it always gives you the biggest (or most urgent) item next. You already know Vectors, and the HashSet page gave you a quick first look at VecDeque. This page goes deeper, and adds BinaryHeap on top.

Why a Vec is a bad queue

You can use a Vec as a queue. Add with push, take from the front with remove(0). It works. The problem is what happens behind the scenes.

A Vec keeps its items packed together, starting at position 0. When you remove the first item, every other item has to slide one step to the left to fill the gap. With 3 items, nobody notices. With 100,000 items, every single remove(0) moves 99,999 values. That’s what “O(n)” means: the work grows with the size of the list.

A VecDeque (say “vec deck”, short for double-ended queue) solves this with a ring buffer. Picture a round table with numbered seats, and a little sign saying “the line starts here”. When the first person leaves, nobody stands up. You just move the sign to the next seat. When someone new arrives and the last seat is taken, they sit in seat 0 if it’s free, wrapping around the table. Adding or removing at either end is just “move the sign” or “fill one seat”, so it takes the same tiny amount of time no matter how long the line is. That’s “O(1)”.

use std::collections::VecDeque;

fn main() {
    // A Vec used as a queue: it works, but remove(0) shifts everyone left.
    let mut vec_line = vec!["Ana", "Ben", "Cai"];
    let served = vec_line.remove(0);
    println!("Vec served {served}, still waiting: {:?}", vec_line);

    // A VecDeque: pop_front just moves its "start" marker.
    let mut deque_line = VecDeque::from(vec!["Ana", "Ben", "Cai"]);
    let served = deque_line.pop_front();
    println!("VecDeque served {:?}, still waiting: {:?}", served, deque_line);
}

Output:

Vec served Ana, still waiting: ["Ben", "Cai"]
VecDeque served Some("Ana"), still waiting: ["Ben", "Cai"]

▶ Try it Yourself

The result looks the same. The difference is speed, and it only shows up when the line gets long. Notice one more thing: pop_front returns an Option. If the line is empty, you get None instead of a crash.

VecDeque basics

VecDeque lives in std::collections, so you need a use line. After that, the methods read almost like English: push or pop, at the front or the back.

use std::collections::VecDeque;

fn main() {
    let mut deque: VecDeque<i32> = VecDeque::new();
    deque.push_back(2);
    deque.push_back(3);
    deque.push_front(1);
    println!("{:?}", deque);

    println!("front: {:?}, back: {:?}", deque.front(), deque.back());
    println!("len: {}, empty: {}", deque.len(), deque.is_empty());
    println!("deque[1] = {}", deque[1]);
    println!("get(9) = {:?}", deque.get(9));

    let first = deque.pop_front();
    let last = deque.pop_back();
    println!("popped {:?} and {:?}, left: {:?}", first, last, deque);
}

Output:

[1, 2, 3]
front: Some(1), back: Some(3)
len: 3, empty: false
deque[1] = 2
get(9) = None
popped Some(1) and Some(3), left: [2]

▶ Try it Yourself

front and back let you look without removing. Indexing with deque[1] works just like a Vec, and it panics if the index is too big, so use get when you’re not sure.

You can also build a VecDeque from a Vec, loop over it, and turn it back into a Vec or a slice when another function needs one:

use std::collections::VecDeque;

fn main() {
    let mut playlist = VecDeque::from(vec!["Intro", "Verse", "Chorus"]);
    playlist.push_front("Count-in");
    playlist.push_back("Outro");

    for (i, song) in playlist.iter().enumerate() {
        println!("{}. {}", i + 1, song);
    }

    // Need a normal slice? make_contiguous lines everything up in memory.
    let songs = playlist.make_contiguous();
    songs.sort();
    println!("sorted: {:?}", songs);

    // Or turn the whole thing back into a Vec.
    let as_vec: Vec<&str> = playlist.into();
    println!("as a Vec: {:?}", as_vec);
}

Output:

1. Count-in
2. Intro
3. Verse
4. Chorus
5. Outro
sorted: ["Chorus", "Count-in", "Intro", "Outro", "Verse"]
as a Vec: ["Chorus", "Count-in", "Intro", "Outro", "Verse"]

▶ Try it Yourself

Why is make_contiguous needed? Remember the round table: after some wrapping around, the items might sit in two separate pieces of memory. make_contiguous tidies them into one piece and hands you a normal slice, so you can use slice tools like sort. You won’t need it often, but it’s good to know it exists.

Real uses for VecDeque

Here are three everyday jobs where a VecDeque fits perfectly.

A first-in, first-out task queue. Print jobs wait in line. New jobs go to the back, the printer takes from the front. An urgent job can still skip ahead with push_front:

use std::collections::VecDeque;

fn main() {
    let mut print_queue = VecDeque::new();
    print_queue.push_back("report.pdf");
    print_queue.push_back("photo.jpg");
    print_queue.push_back("invoice.pdf");

    // Urgent! This one jumps to the front of the line.
    print_queue.push_front("boarding-pass.pdf");

    while let Some(job) = print_queue.pop_front() {
        println!("Printing {job} ({} still waiting)", print_queue.len());
    }
    println!("All done. Queue empty: {}", print_queue.is_empty());
}

Output:

Printing boarding-pass.pdf (3 still waiting)
Printing report.pdf (2 still waiting)
Printing photo.jpg (1 still waiting)
Printing invoice.pdf (0 still waiting)
All done. Queue empty: true

▶ Try it Yourself

while let Some(job) = ...pop_front() is the classic queue loop. It keeps going until pop_front returns None, which means the line is empty. (See if let if this shape is new to you.)

A “last N items” history. A search box that remembers your 3 most recent searches. When it’s full, the oldest one falls off the front:

use std::collections::VecDeque;

const MAX_RECENT: usize = 3;

fn remember(recent: &mut VecDeque<String>, search: &str) {
    if recent.len() == MAX_RECENT {
        recent.pop_front(); // forget the oldest search
    }
    recent.push_back(search.to_string());
}

fn main() {
    let mut recent = VecDeque::with_capacity(MAX_RECENT);

    for search in ["rust book", "vecdeque", "binary heap", "pizza near me"] {
        remember(&mut recent, search);
        println!("{:?}", recent);
    }

    // Show newest first, like a search box would.
    let newest_first: Vec<&String> = recent.iter().rev().collect();
    println!("newest first: {:?}", newest_first);
}

Output:

["rust book"]
["rust book", "vecdeque"]
["rust book", "vecdeque", "binary heap"]
["vecdeque", "binary heap", "pizza near me"]
newest first: ["pizza near me", "binary heap", "vecdeque"]

▶ Try it Yourself

A sliding window average. A thermometer sends a reading every minute, and you want the average of the last 3. Each new reading joins at the back, and the oldest leaves at the front. Keeping a running sum means you never have to add up the whole window again:

use std::collections::VecDeque;

fn main() {
    let readings = [20.0, 22.0, 24.0, 23.0, 19.0, 21.0];
    let window_size = 3;
    let mut window: VecDeque<f64> = VecDeque::new();
    let mut sum = 0.0;

    for reading in readings {
        window.push_back(reading);
        sum += reading;

        if window.len() > window_size {
            sum -= window.pop_front().unwrap(); // the oldest reading leaves
        }

        if window.len() == window_size {
            let average = sum / window_size as f64;
            println!("{:?} -> average {:.1}", window, average);
        }
    }
}

Output:

[20.0, 22.0, 24.0] -> average 22.0
[22.0, 24.0, 23.0] -> average 23.0
[24.0, 23.0, 19.0] -> average 22.0
[23.0, 19.0, 21.0] -> average 21.0

▶ Try it Yourself

The unwrap() is safe here: we only pop when the window has more than 3 items, so it can’t be empty.

BinaryHeap: always the biggest next

Now the hospital waiting room. Sometimes you don’t care who came first. You want “give me the most important thing next”, again and again, while new things keep arriving.

You could push everything into a Vec and sort it each time. But sorting everything just to find the top item is a lot of wasted work. A BinaryHeap keeps its items only loosely organised, just enough that the biggest one is always on top. Adding an item or taking the top one is cheap (O(log n), which grows very slowly: about 17 steps for 100,000 items).

Rust’s BinaryHeap is a max-heap: pop always gives you the largest value. Here are the bids at an auction:

use std::collections::BinaryHeap;

fn main() {
    let mut bids = BinaryHeap::new();
    bids.push(120);
    bids.push(450);
    bids.push(80);
    bids.push(300);

    println!("highest bid: {:?}", bids.peek());
    println!("number of bids: {}", bids.len());

    while let Some(bid) = bids.pop() {
        println!("next: {bid}");
    }

    let heap = BinaryHeap::from(vec![5, 1, 4, 2, 3]);
    println!("sorted: {:?}", heap.into_sorted_vec());
}

Output:

highest bid: Some(450)
number of bids: 4
next: 450
next: 300
next: 120
next: 80
sorted: [1, 2, 3, 4, 5]

▶ Try it Yourself

peek looks at the top without removing it. pop removes it. into_sorted_vec uses up the heap and gives you a Vec sorted from smallest to largest. Like VecDeque, both peek and pop return an Option, so an empty heap is never a crash.

Min-heaps with Reverse

What if you want the smallest first? The closest delivery stop, the cheapest flight, the earliest deadline. You don’t need a different collection. Wrap each value in std::cmp::Reverse, which simply flips the comparison: what was biggest is now smallest.

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

fn main() {
    // Delivery stops, by distance in km. Always drive to the closest next.
    let mut stops = BinaryHeap::new();
    for km in [12, 3, 8, 5] {
        stops.push(Reverse(km));
    }

    if let Some(Reverse(closest)) = stops.peek() {
        println!("closest stop: {closest} km");
    }

    while let Some(Reverse(km)) = stops.pop() {
        println!("drive {km} km");
    }
}

Output:

closest stop: 3 km
drive 3 km
drive 5 km
drive 8 km
drive 12 km

▶ Try it Yourself

Reverse(km) is a tiny wrapper struct. The pattern Some(Reverse(km)) unwraps both layers in one go, so you get the plain number back.

A priority queue of structs

Real tasks aren’t just numbers. They have a name, a priority, maybe an arrival time. To put your own struct in a BinaryHeap, Rust needs to know how to compare two of them, which means the struct must implement Ord (see Common Traits).

The quickest way is derive. One thing to know: derive compares fields from top to bottom. It compares the first field, and only looks at the second field if the first ones are equal. So put the field you want to sort by first:

use std::collections::BinaryHeap;

// Field order matters: derive compares `priority` first, then `name`.
#[derive(Debug, PartialEq, Eq, PartialOrd, Ord)]
struct Task {
    priority: u8,
    name: String,
}

fn main() {
    let mut todo = BinaryHeap::new();
    todo.push(Task { priority: 2, name: "book dentist".to_string() });
    todo.push(Task { priority: 5, name: "fix the outage".to_string() });
    todo.push(Task { priority: 1, name: "water plants".to_string() });
    todo.push(Task { priority: 2, name: "reply to email".to_string() });

    while let Some(task) = todo.pop() {
        println!("[{}] {}", task.priority, task.name);
    }
}

Output:

[5] fix the outage
[2] reply to email
[2] book dentist
[1] water plants

▶ Try it Yourself

If you swapped the two fields so name came first, the heap would order tasks alphabetically and ignore priority almost completely. Easy mistake, quiet bug.

Look at the two priority-2 tasks. “book dentist” arrived first, but “reply to email” came out first. The tie was broken by name, and “reply” beats “book” because it comes later in the alphabet. That’s predictable, but probably not what you want. Usually, on a tie, the task that arrived first should go first. For that kind of custom rule, write Ord yourself:

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

#[derive(Debug, PartialEq, Eq)]
struct Job {
    priority: u8,
    id: u32, // arrival order: a lower id arrived earlier
    name: String,
}

impl Ord for Job {
    fn cmp(&self, other: &Self) -> Ordering {
        self.priority
            .cmp(&other.priority) // higher priority wins
            .then_with(|| other.id.cmp(&self.id)) // on a tie, the earlier id wins
    }
}

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

fn main() {
    let mut jobs = BinaryHeap::new();
    jobs.push(Job { priority: 2, id: 1, name: "book dentist".to_string() });
    jobs.push(Job { priority: 5, id: 2, name: "fix the outage".to_string() });
    jobs.push(Job { priority: 1, id: 3, name: "water plants".to_string() });
    jobs.push(Job { priority: 2, id: 4, name: "reply to email".to_string() });

    while let Some(job) = jobs.pop() {
        println!("[{}] #{} {}", job.priority, job.id, job.name);
    }
}

Output:

[5] #2 fix the outage
[2] #1 book dentist
[2] #4 reply to email
[1] #3 water plants

▶ Try it Yourself

The trick is in then_with: if the priorities are equal, compare the ids backwards (other.id against self.id). That makes the smaller id count as “bigger”, so it comes out of the max-heap first. Don’t worry if this takes a minute to sink in. Flipping the comparison is exactly what Reverse does for you, just written out by hand. The PartialOrd block is always the same boilerplate: it just calls your cmp.

A real algorithm: the top 3 scores

Say you have a huge list of game scores and you only want the top 3. Sorting the whole list works, but there’s a neat trick that only ever keeps 3 items around.

Use a min-heap of size 3. Push each score. When the heap has 4 items, pop one. Because it’s a min-heap, the one you throw away is the smallest. At the end, only the 3 best are left.

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

fn main() {
    let scores = [72, 95, 64, 88, 91, 55, 99, 80];
    let mut top = BinaryHeap::new(); // a min-heap: the smallest score sits on top

    for score in scores {
        top.push(Reverse(score));
        if top.len() > 3 {
            top.pop(); // four is one too many: drop the smallest
        }
    }

    let best: Vec<u32> = top
        .into_sorted_vec()
        .into_iter()
        .map(|Reverse(score)| score)
        .collect();
    println!("top 3: {:?}", best);
}

Output:

top 3: [99, 95, 91]

▶ Try it Yourself

A nice bonus: into_sorted_vec sorts the Reverse values from “smallest” to “largest”, which for the real scores means largest to smallest. So the best score comes out first, with no extra sorting. This pattern works for a list of a million scores while only ever holding 4 in memory.

Which one should I use?

Here’s a cheat sheet. “Fast” means the time stays about the same however big the collection gets. “Slow” means it grows with the size.

Collection	Great at	Push	Take from the front / top	Find any item
`Vec<T>`	A list you read by position; a stack	Fast at the end	Slow (`remove(0)` shifts everything)	Slow (look at each item)
`VecDeque<T>`	Queues: add and remove at both ends	Fast at both ends	Fast at both ends	Slow (look at each item)
`BinaryHeap<T>`	“Give me the biggest / most urgent next”	Fast-ish (O(log n))	Fast-ish: always the largest	Slow, and no sorted order
`BTreeSet<T>`	Unique values, always kept sorted	Fast-ish (O(log n))	Fast-ish: smallest and largest	Fast-ish (O(log n))

When in doubt, start with a Vec. Reach for a VecDeque when you take things off the front. Reach for a BinaryHeap when you keep asking “what’s most important now?”. Use a BTreeSet when you need sorted, unique values and want to look items up, not just take the top one.

Common mistakes

Expecting .iter() on a BinaryHeap to be sorted. A heap is only loosely ordered. The biggest item is first, but the rest are in a jumbled order that’s useful to the heap, not to you:

use std::collections::BinaryHeap;

fn main() {
    let heap = BinaryHeap::from(vec![1, 5, 2, 8, 3, 9]);

    println!("iter:   {:?}", heap.iter().collect::<Vec<_>>());
    println!("sorted: {:?}", heap.clone().into_sorted_vec());

    let mut heap = heap;
    print!("popped:");
    while let Some(n) = heap.pop() {
        print!(" {n}");
    }
    println!();
}

Output:

iter:   [9, 8, 2, 5, 3, 1]
sorted: [1, 2, 3, 5, 8, 9]
popped: 9 8 5 3 2 1

▶ Try it Yourself

The same goes for printing a heap with {:?}: you’ll see the internal jumble. If you need the items in order, pop them one by one or call into_sorted_vec.

Putting a struct without Ord into a BinaryHeap. The heap must compare items to know which one goes on top. If your struct can’t be compared, Rust stops you:

use std::collections::BinaryHeap;

struct Ticket {
    urgency: u8,
    title: String,
}

fn main() {
    let mut tickets = BinaryHeap::new();
    tickets.push(Ticket { urgency: 3, title: "login broken".to_string() });
}

error[E0277]: the trait bound `Ticket: Ord` is not satisfied
  --> src/main.rs:10:13
   |
10 |     tickets.push(Ticket { urgency: 3, title: "login broken".to_string() });
   |             ^^^^ the trait `Ord` is not implemented for `Ticket`
   |
help: consider annotating `Ticket` with `#[derive(Ord)]`

The fix is to add #[derive(PartialEq, Eq, PartialOrd, Ord)] above the struct (Ord needs the other three too), with urgency as the first field. Or write Ord by hand, like the Job example above.

Practice

1. Taking turns

Three friends, Ana, Ben and Cai, take turns in a board game. Put them in a VecDeque and print who plays on turns 1 to 5. After each turn, the player goes to the back of the line. Hint: pop_front the player, print them, then push_back the same player.

Show solution

use std::collections::VecDeque;

fn main() {
    let mut players = VecDeque::from(vec!["Ana", "Ben", "Cai"]);

    for turn in 1..=5 {
        let player = players.pop_front().unwrap();
        println!("Turn {turn}: {player}");
        players.push_back(player); // back to the end of the line
    }
}

Output:

Turn 1: Ana
Turn 2: Ben
Turn 3: Cai
Turn 4: Ana
Turn 5: Ben

▶ Try it Yourself

The front and back are both fast in a VecDeque, so rotating the line costs almost nothing, no matter how many players there are.

2. The emergency room

Patients arrive with a severity from 1 to 5. The most severe goes first. If two patients have the same severity, whoever arrived first goes first. Use a BinaryHeap of tuples and print the order patients are seen. Patients: Mia (severity 2, arrived 1st), Leo (5, 2nd), Sam (2, 3rd), Zoe (4, 4th). Hint: tuples compare field by field, just like a derived struct. Try (severity, Reverse(arrival), name).

Show solution

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

fn main() {
    // (severity, Reverse(arrival), name)
    let mut waiting = BinaryHeap::new();
    waiting.push((2, Reverse(1), "Mia"));
    waiting.push((5, Reverse(2), "Leo"));
    waiting.push((2, Reverse(3), "Sam"));
    waiting.push((4, Reverse(4), "Zoe"));

    while let Some((severity, Reverse(arrival), name)) = waiting.pop() {
        println!("{name} (severity {severity}, arrived #{arrival})");
    }
}

Output:

Leo (severity 5, arrived #2)
Zoe (severity 4, arrived #4)
Mia (severity 2, arrived #1)
Sam (severity 2, arrived #3)

▶ Try it Yourself

Severity is compared first, so Leo goes first. Mia and Sam tie on severity, so Reverse(arrival) decides, and the earlier arrival (Mia) wins. Because every arrival number is different, the name is never needed to break a tie.

Recap

A Vec is a poor queue: remove(0) shifts every other item. A VecDeque is a ring buffer with fast push/pop at both ends.
Use VecDeque for first-in-first-out queues, “last N items” histories, and sliding windows.
A BinaryHeap is a max-heap: pop and peek always give the largest item, without sorting everything.
Wrap values in std::cmp::Reverse to get a min-heap (smallest first).
Structs in a heap need Ord. With derive, fields are compared top to bottom, so put the priority first. Write Ord by hand for custom tie-breaks.
.iter() on a heap is not sorted. Pop items one by one, or use into_sorted_vec.

Quick check

1. Why is VecDeque::pop_front faster than Vec::remove(0) on a long list?

2. You push 4, 9 and 2 into a BinaryHeap. What does the first pop() return?

3. How do you make a BinaryHeap give you the smallest value first?

4. A struct derives Ord with fields name then priority. What decides the order in a BinaryHeap?

Score: 0 / 4

std::collections — standard library docs: the official “when should you use which collection?” guide, with a speed table for every collection.
VecDeque — standard library docs: every method, including rotate_left, range, retain and as_slices.
BinaryHeap — standard library docs: every heap method, plus examples of min-heaps with Reverse and of peek_mut.
Reverse — standard library docs: the tiny wrapper that flips any comparison, with examples of sorting in reverse order.
Common Collections — The Rust Book: the Book’s chapter on vectors, strings and hash maps, the collections you’ll use alongside these.

Rust VecDeque & BinaryHeap

Why a Vec is a bad queue

VecDeque basics

Real uses for VecDeque

BinaryHeap: always the biggest next

Min-heaps with Reverse

A priority queue of structs

A real algorithm: the top 3 scores

Which one should I use?

Common mistakes

Practice

1. Taking turns

2. The emergency room

Recap

Quick check

Read more