BinaryHeap, stacks and queues

A priority queue returns the largest value first, whatever the insertion order, and that rule is the whole difference from a stack or a queue. Rust spells it BinaryHeap, and it is the container behind a scheduler, a shortest-path search and any "take the best next" loop. A stack and a queue are the same idea with a different rule, and both are built from the sequence types of the previous lessons.

This lesson covers the max-heap, the min-heap that Reverse produces, the stack over a vector and the queue over a deque. The last section reads the error for a heap of floats, which is the same trait rule the sets followed.

A max-heap

push inserts a value and pop removes the largest one, in logarithmic time. The heap keeps its own order inside the vector it wraps, so iterating it does not give a sorted sequence; the pop does.

The program pushes three numbers and pops all three. The outputs are nine, four and three, which is the order a max-heap promises.

use std::collections::BinaryHeap; fn main() { let mut heap = BinaryHeap::new(); for value in [3, 9, 4] { heap.push(value); } println!("{:?}", heap.pop()); println!("{:?}", heap.pop()); println!("{:?}", heap.pop()); }

rustc --edition 2024 heap.rs
./heap

Some(9)
Some(4)
Some(3)

The heap does not sort its storage: iter walks the internal vector in whatever order it happens to be, which is why a report should pop or sort rather than iterate. The push and pop cost a logarithm, and building a heap from a vector with from costs only a linear pass. Popping everything is a heap sort, and it is the cheapest way to see the order. The lesson on sorting compares it with a full sort of the same values.

A min-heap with Reverse

A heap always keeps the greatest value, so a min-heap stores Reverse(value): the wrapper reverses the comparison, and the greatest reversed value is the smallest original one. The same trick works for any type with an ordering.

The program pushes three values as reversed numbers and pops them in a loop. The output is ascending, which is the min-heap order.

use std::cmp::Reverse; use std::collections::BinaryHeap; fn main() { let mut heap = BinaryHeap::new(); for value in [3, 9, 4] { heap.push(Reverse(value)); } while let Some(Reverse(value)) = heap.pop() { print!("{value} "); } println!(); }

rustc --edition 2024 min_heap.rs
./min_heap

3 4 9

The pattern match in the loop unwraps the wrapper, so the printed value is the original one. Reverse is a zero-cost wrapper, which the lesson on tuple structs explains.

A stack over a Vec

A vector already is a stack: push adds at the end and pop removes from it, and last peeks. There is no separate type because the vector's end is the cheap end.

The program pushes two values and pops one, then peeks at the other. The outputs are the popped value and the remaining one.

fn main() { let mut stack = Vec::new(); stack.push("a"); stack.push("b"); println!("{:?}", stack.pop()); println!("{:?}", stack.last()); }

rustc --edition 2024 stack.rs
./stack

Some("b")
Some("a")

A depth-first walk uses exactly this pair, and the lesson on directories drains a stack of paths.

A queue over a VecDeque

A queue adds at the back and removes from the front, so the deque from the previous lesson is the container. push_back and pop_front are both constant time, which a vector cannot offer.

The program queues two values and takes one from the front. The output is the first value in and the remaining one.

use std::collections::VecDeque; fn main() { let mut queue = VecDeque::new(); queue.push_back("a"); queue.push_back("b"); println!("{:?}", queue.pop_front()); println!("{:?}", queue.front()); }

rustc --edition 2024 queue.rs
./queue

Some("a")
Some("b")

A queue of work items is the shape of every scheduler, and a deque gives it without shifting. The queue and the stack differ in one method name, and the choice of container is what makes it cheap. The lesson on VecDeque shows the rest of the API.

A heap of floats

BinaryHeap needs Ord, and a float does not implement it. The insert is E0277, and the message names the trait and the method, which is the same error the set produced for the same reason.

The program pushes a float into a heap. The fix is a key type with an ordering, such as the bit pattern in an integer, or a wrapper that defines one.

use std::collections::BinaryHeap; fn main() { let mut heap = BinaryHeap::new(); heap.push(1.5); println!("{}", heap.len()); }

rustc --edition 2024 float_heap_err.rs

error[E0277]: the trait bound `{float}: Ord` is not satisfied
--> float_heap_err.rs:5:10
|
5 | heap.push(1.5);
| ^^^^ the trait `Ord` is not implemented for `{float}`
|
= help: the following other types implement trait `Ord`:
i128
i16
i32
i64
i8
isize
u128
u16
and 4 others
note: required by a bound in `BinaryHeap::<T, A>::push`
--> /rustc/31fca3adb283cc9dfd56b49cdee9a96eb9c96ffd/library/alloc/src/collections/binary_heap/mod.rs:747:4

error: aborting due to 1 previous error

For more information about this error, try `rustc --explain E0277`.

The same rule applies to a sorted collection and to a set. The lesson on operator traits shows where Ord and PartialOrd come from.

Exercises

  1. Push five numbers into a max-heap and print them in descending order.
  2. Build a min-heap with Reverse and print the same numbers ascending.
  3. Use a stack to reverse a vector of words without calling reverse.

Questions

A new set of questions in a new order every time. Choose one answer for each, then check.

  1. What does BinaryHeap::pop return?

    Answer

    The largest value

    The heap keeps the greatest value at the top, so pop removes that one.

  2. How is a min-heap built?

    Answer

    By wrapping the values in Reverse

    Reverse flips the comparison, so the greatest reversed value is the smallest original.

  3. What makes a Vec a stack?

    Answer

    push and pop work at the end

    The end of the vector is the cheap end, which is what a stack needs.

  4. Which container is the natural queue?

    Answer

    VecDeque

    A deque removes from the front in constant time, which a vector cannot.

  5. What does this program print? use std::collections::BinaryHeap; fn main() { let mut heap = BinaryHeap::new(); for value in [3, 9, 4] { heap.push(value); } println!("{:?}", heap.pop()); println!("{:?}", heap.pop()); println!("{:?}", heap.pop()); }

    Answer

    Some(9) / Some(4) / Some(3)

    The pops come out largest first, which is the max-heap order.

  6. What does this program print? use std::cmp::Reverse; use std::collections::BinaryHeap; fn main() { let mut heap = BinaryHeap::new(); for value in [3, 9, 4] { heap.push(Reverse(value)); } while let Some(Reverse(value)) = heap.pop() { println!("{value}"); } }

    Answer

    3 / 4 / 9

    The reversed comparison turns the max-heap into a min-heap, so the smallest comes first.

  7. What does this program print? fn main() { let mut stack = Vec::new(); stack.push("a"); stack.push("b"); println!("{:?}", stack.pop()); println!("{:?}", stack.last()); }

    Answer

    Some("b") / Some("a")

    The last value pushed comes out first, and the remaining one is a.

  8. What does this program print? use std::collections::VecDeque; fn main() { let mut queue = VecDeque::new(); queue.push_back("a"); queue.push_back("b"); println!("{:?}", queue.pop_front()); println!("{:?}", queue.front()); }

    Answer

    Some("a") / Some("b")

    The queue takes the first value in, and b is next in line.

  9. What is the first line of the compiler output for this program? use std::collections::BinaryHeap; fn main() { let mut heap = BinaryHeap::new(); heap.push(1.5); println!("{}", heap.len()); }

    Answer

    error[E0277]: the trait bound {float}: Ord is not satisfied

    The heap orders its values, and a float has no total order to use.

  10. What does this program print? use std::collections::BinaryHeap; fn main() { let mut heap = BinaryHeap::from(vec![1, 5, 3]); println!("{}", heap.peek().unwrap()); println!("{}", heap.len()); }

    Answer

    5 / 3

    peek returns the greatest value without removing it, so the heap still holds three.

The code on this page was built with rustc 1.96.1 and run on Alpine Linux 3.24.3 (x86_64) in a Docker container.

Article author: Arthur Isaev

Banner image