Skip to content
Tutorials Center
My learning

Topics

Lesson 50 of 132 ยท Collections and Iterators

VecDeque, BinaryHeap and Other Collections

Learn Rust's other collections - VecDeque ring buffer, BinaryHeap priority queue with Reverse, why LinkedList is rare, BTreeMap range queries and a table for choosing the right collection.

Vec, String and HashMap cover most programs. But some problems have a shape that those three handle badly: a queue where items leave from the front, a to-do list where the most urgent job must come out first, or a timeline where you ask "what happened between 10:00 and 11:00?". The standard library has a collection for each of these, and picking the right one often turns a slow or clumsy program into a short, fast one.

This lesson covers VecDeque (a double-ended queue), BinaryHeap (a priority queue), LinkedList (and why you will rarely use it), range queries on BTreeMap, and ends with a table that helps you choose. All of them live in std::collections. The next lesson shows how to loop over any of them with iterators.

VecDeque: a queue with two open ends

A Vec is fast at the back but slow at the front: remove(0) shifts every element one place to the left. If you use a Vec as a queue (add at the back, take from the front), every dequeue costs O(n).

VecDeque<T> (pronounced "vec-deck", for double-ended queue) fixes this. It is a ring buffer: one contiguous block of memory used as a circle, plus an index saying where the first element is. Adding or removing at either end only moves that index, so both ends are O(1).

Picture a buffer with room for 8 items. Pushing at the back writes after the last item; pushing at the front moves the start index backwards, wrapping around to the end of the buffer if needed. No elements are copied.

Rust VecDeque as a queue and a deque

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with io::stdin().read_line()), it gets the next line from this box.

Indexing with queue[i] works, in O(1), but the elements might be stored in two pieces (the ring wraps around). That is why you cannot get a single &[T] slice for free. When you need one, call make_contiguous(), which rearranges the buffer and returns a mutable slice, or as_slices() to see the two parts.

Rust Two slices and make_contiguous

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with io::stdin().read_line()), it gets the next line from this box.

The exact split between a and b depends on how the buffer grew, so do not rely on it (in this run it happened to be 2 and 2). A Vec can be turned into a VecDeque with VecDeque::from(vec) and back with Vec::from(deque).

A queue is the heart of breadth-first search: visit the start, then everything one step away, then everything two steps away. Here is a shortest-path search on a small grid. # is a wall; we count the steps from S to E.

Rust Shortest path in a maze with a VecDeque

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with io::stdin().read_line()), it gets the next line from this box.

wrapping_sub(1) turns 0 - 1 into a huge number instead of panicking, and the bounds test nr < rows then rejects it. Using a Vec here with remove(0) would work too but would slow down on big grids.

Bounded buffers

A very common pattern is "remember only the last N items". Push at the back, and when the length exceeds N, pop from the front:

Rust A fixed-size history with VecDeque

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with io::stdin().read_line()), it gets the next line from this box.

BinaryHeap: always get the biggest item first

A BinaryHeap<T> is a priority queue. You can push items in any order, and pop always returns the greatest item according to Ord. Pushing and popping cost O(log n), and looking at the top with peek is O(1). Internally it is a binary tree stored in a Vec, arranged so that every parent is at least as large as its children (a "max-heap").

Rust A max-heap

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with io::stdin().read_line()), it gets the next line from this box.

The numbers come out as 9 8 5 3 2 1: largest first. into_sorted_vec returns an ascending vector.

Iterating over a BinaryHeap with for x in &heap or .iter() visits the elements in arbitrary order, not sorted order, and printing it with {:?} shows the internal layout. Only pop (repeatedly) or into_sorted_vec gives sorted output.

A min-heap with Reverse

Rust's heap is a max-heap. To get the smallest item first, wrap items in std::cmp::Reverse, which flips the comparison:

Rust Min-heap with Reverse

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with io::stdin().read_line()), it gets the next line from this box.

Priority queue of your own type

For a struct, implement Ord (and PartialOrd, Eq, PartialEq) so the field that defines priority decides. Remember that BinaryHeap pops the greatest, so if a smaller number should mean "more urgent", reverse the comparison inside cmp.

Rust Tasks ordered by urgency

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with io::stdin().read_line()), it gets the next line from this box.

Both urgency-1 tasks come first, and the tie is broken by name (the greater name pops first, so hotfix comes before alert). The heap does not keep equal items in insertion order, which is why a tie-breaker is worth adding. Floating-point numbers do not implement Ord, so a heap of f64 needs a wrapper (for instance one that uses total_cmp).

Where heaps shine: Dijkstra and top-k

The two classic uses are shortest paths in weighted graphs (Dijkstra's algorithm) and "give me the k largest/smallest of a huge stream". For the second, keep a heap of size k, and discard anything that cannot make the cut:

Rust The three largest numbers of a stream

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with io::stdin().read_line()), it gets the next line from this box.

This uses O(k) memory and O(n log k) time, much better than sorting the whole input when n is large and k is small.

LinkedList: the collection you will rarely want

std::collections::LinkedList<T> is a doubly linked list: each element lives in its own heap node with pointers to its neighbors. It offers O(1) push_front, push_back, pop_front, pop_back, and O(1) splicing of two lists with append.

Rust LinkedList basics

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with io::stdin().read_line()), it gets the next line from this box.

That looks attractive, so why is it rarely used?

  • Every element is a separate allocation, so memory use is higher and creating the list is slow.
  • Nodes are scattered in memory. A modern CPU is fast at reading neighboring memory and slow at chasing pointers, so walking a linked list is several times slower than walking a Vec or VecDeque.
  • There is no O(1) indexing, and inserting in the middle still needs O(n) to find the position.

In practice VecDeque beats LinkedList for queues, and Vec beats it for nearly everything else. The standard library documentation itself recommends Vec or VecDeque in almost every case. A linked list is only worth considering when you really need cheap splitting and joining of large lists. Linked lists are also a famous beginner exercise in Rust because of ownership; you will write one in building data structures with unsafe.

BTreeMap in depth: ranges and ordered operations

BTreeMap keeps its keys sorted, which gives you operations a hash map cannot offer: range queries, first and last keys, and splitting at a key.

Rust Range queries on a BTreeMap

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with io::stdin().read_line()), it gets the next line from this box.

range(..) accepts any Rust range expression, and (Bound, Bound) pairs for more exotic edges. Finding the closest key below or above a value (range(..x).next_back() and range(x..).next()) is the classic "predecessor/successor" query, handy for things like finding which interval a number falls into.

BTreeSet has the same range method, plus the set operations from the previous lesson. Both types give O(log n) lookups; each node stores many keys in a small array, so a B-tree uses cache better than a binary tree would.

Choosing a collection

You need Use Insert / remove Lookup Notes
A growable list, fast iteration Vec<T> O(1) at end, O(n) elsewhere O(1) by index The default choice
A queue or both-ends access VecDeque<T> O(1) at both ends O(1) by index Ring buffer
The largest/smallest item next BinaryHeap<T> O(log n) O(1) peek top only Priority queue
Find by key HashMap<K, V> O(1) average O(1) average Unordered
Unique values, fast membership HashSet<T> O(1) average O(1) average Unordered
Sorted keys, ranges BTreeMap<K, V> O(log n) O(log n) Sorted iteration
Sorted unique values BTreeSet<T> O(log n) O(log n) Sorted iteration
Cheap list splicing (rare) LinkedList<T> O(1) at ends O(n) Usually not worth it

A good decision process: start with Vec. If you remove from the front, use VecDeque. If you look things up by key, use HashMap (or BTreeMap if you need order or ranges). If you need "next best item", use BinaryHeap. Only measure and change further if profiling shows a problem. For small collections (up to a few dozen items) a plain Vec with a linear search is often the fastest option of all, because its data sits next to each other in memory.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Why is VecDeque better than Vec for a first-in-first-out queue?

    A VecDeque only moves its start index when you remove from the front. A Vec has to slide every remaining element one place.
  2. 2. Which item does BinaryHeap::pop return?

    BinaryHeap is a max-heap. Wrap items in std::cmp::Reverse to get the smallest first.
  3. 3. What does iterating over a BinaryHeap with .iter() give you?

    Only pop and into_sorted_vec give sorted order. Iterators visit the underlying vector layout, which is not sorted.
  4. 4. Which collection lets you ask for all entries with keys between 600 and 780?

    BTreeMap keeps keys sorted, so range queries are efficient. A HashMap has no order to search by.
  5. 5. Why is LinkedList rarely the best choice in Rust?

    Linked lists have poor cache behavior and higher memory overhead. VecDeque gives the same O(1) operations at both ends with far better speed.

Summary

  • VecDeque<T> is a ring buffer with O(1) push and pop at both ends and O(1) indexing. Use it for queues, breadth-first search and bounded histories.
  • BinaryHeap<T> is a max-heap priority queue: O(log n) push/pop, O(1) peek. Use Reverse for a min-heap and implement Ord for custom priorities. Iteration order is arbitrary.
  • LinkedList<T> has O(1) ends and splicing but poor cache behavior; prefer Vec or VecDeque.
  • BTreeMap/BTreeSet keep keys sorted and support range, first_key_value, pop_first and split_off.
  • Start with Vec, then choose by how you access the data: front, priority, key, or range.

Next: Iterators