Priority Queues in Rust

About This Module

This module introduces priority queues, a fundamental data structure that serves elements based on their priority rather than insertion order. We'll explore Rust's BinaryHeap implementation, custom ordering with structs, and analyze the time complexity of various priority queue operations.

Prework

Prework Reading

Read the following sections from "The Rust Programming Language" book:

Pre-lecture Reflections

Before class, consider these questions:

How do priority queues differ from regular FIFO queues in their use cases?
What are some real-world applications where priority-based ordering is essential?
How does the Ord trait enable custom priority ordering in Rust?
What trade-offs exist between different priority queue implementations?
When would you choose a priority queue over sorting all elements at once?

Lecture

Learning Objectives

By the end of this module, you should be able to:

Understand the difference between standard queues and priority queues
Use Rust's BinaryHeap for priority queue operations
Implement custom ordering with structs using derive and manual trait implementation
Apply the Reverse wrapper to change ordering behavior
Analyze time complexity of priority queue operations
Design priority-based systems for real-world applications

Priority Queues

Standard queue:

things returned in order in which they were inserted

Priority queue:

items have priorities
highest priority items returned first

Example of Priority Queue

Triage in a hospital emergency room.

For non-critical injuries, perhaps FIFO, but heart attack gets priority.

Rust standard library implementation: `BinaryHeap<T>`

Priorities provided by the ordering of elements of T (via trait Ord)

Method push(T):
push element onto the heap

Method pop() -> Option<T>:
remove the greatest and return it Some(T) or None

use std::collections::BinaryHeap;

let mut pq = BinaryHeap::new();

pq.push(2);
pq.push(7);
pq.push(3);

println!("{:?}",pq.pop());
println!("{:?}",pq.pop());

pq.push(3);
pq.push(4);

println!("\n{:?}",pq.pop());
println!("{:?}",pq.pop());
println!("{:?}",pq.pop());
println!("{:?}",pq.pop());

Some(7)
Some(3)

Some(4)
Some(3)
Some(2)
None

You can use more complex data types, like your own structs with a priority field, then you have to implement your own Ord trait.

Getting the smallest element out first

Reverse<T>: wrapper that reverses the ordering of elements of a type

3 < 4

true

use std::cmp::Reverse;
Reverse(3) < Reverse(4)

false

5 < 3

false

Reverse(5) < Reverse(3)

true

let mut pq = BinaryHeap::new();

pq.push(Reverse(3));
pq.push(Reverse(1));
pq.push(Reverse(7));

println!("{:?}",pq.pop());
println!("{:?}",pq.pop());

pq.push(Reverse(0));

println!("\n{:?}",pq.pop());
println!("\n{:?}",pq.pop());
println!("\n{:?}",pq.pop());

Some(Reverse(1))
Some(Reverse(3))

Some(Reverse(0))

Some(Reverse(7))

None

How to extract inner value from Reverse()

// Method 1: Using .0 to access the inner value (since Reverse is a tuple struct)
let rev = Reverse(3);
let value = rev.0;  // value = 3
println!("{value}");

// Method 2: Using pattern matching
let rev = Reverse(5);
let Reverse(value) = rev;  // value = 5
println!("{value}");

3
5

Default lexicographic ordering on tuples and structs

Lexicographic ordering:

Compare first elements
If equal, compare second elements
If equal, compare third elements...

Tuples

(3,4) < (2,7)

false

(11,2,7) < (11,3,4)

true

Struct (derive `Ord`)

A custom struct does not support lexicographic ordering, but we can derive traits.

#[derive(PartialEq,Eq,PartialOrd,Ord,Debug)]
struct Point {
    x: i32,
    y: i32,
}

let p = Point{x:3,y:4};
let q = Point{x:2,y:7};
println!("{}", p < q);
println!("{}", p > q);

false
true

let p = Point{x:3,y:4};
let q = Point{x:3,y:7};
println!("{}", p < q);
println!("{}", p > q);

true
false

Another option: implement your own comparison

More complicated, see below
See the documentation for Ord or examples online

#[derive(PartialEq,Eq,Ord,Debug)]
struct Point2 {
    x: i32,
    y: i32,
}

// Let's assume we want to compare point by their distance to the origin
impl std::cmp::PartialOrd for Point2 {
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        // 'Self' (capital) is a shorthand for type Point2
        let this = self.x * self.x + self.y * self.y;
        let that = other.x * other.x + other.y * other.y;
        return this.partial_cmp(&that);  // use the partial_cmp() on integer
    }
}

let p = Point2{x:3,y:1};
let q = Point2{x:2,y:100};
println!("{}", p < q);
println!("{}", p > q);

true
false

Complexity of a priority queue?

Assumptions:

At most $n$ elements
Comparison takes $O (1)$ time

Straightforward

Representation: a vector of elements

Push:

add to the end of the vector
Time complexity: $O (1)$ (amortized) time

Pop:

go over all elements, select the greatest
Time complexity: $O (n)$

DS210 Course Notes