Enhancing Rust’s built-in Queue to become a Priority Queue.

applied.math.coding
3 min readAug 27, 2023

Rust comes with a built-in queue VecDeque. This is a very handy construct and even allows for slicing. Though, if you need a priority queue, there is no such thing provided in Rust’s standard library. Although there exists good crates supporting this feature, I want to give a quick example in this article how one can extend VecDeque to become a priority queue in fact.

Priority queues have there items sorted w.r.t some criteria (the priority). The crucial functionality of a priority queue is the insertion of a new item and having this item correctly placed in the queue.

This operation can be done in log(N) amount of effort, if N refers to the queue’s current size. The reason why it can be done so quick is due to the fact that items are sorted on the queue. Therefore, a binary search can be used to find a new item’s correct position. In every step of a binary search the amount of data searched through is divided by 2. Therefore, in at most 2^m steps, where m = log(N), the position must have been found.

To extend the VecDeque we can use a trait like so:

use std::collections::VecDeque;

pub trait PriorityInsert<T>
where
T: Ord,
{
fn priority_insert(&mut self, v: T);
}

Ord is the trait that makes T implementing the operators <, >, <=, >=. This presents the priority defined on T. For instance, u32 satisfies this boundary. This makes our priority queue being able to operate on very generic types.

The method priority_insert inserts a new value v into the queue at the correct position. We can implement PriorityInsert for VecDeque like so:

use std::collections::VecDeque;

impl<T> PriorityInsert<T> for VecDeque<T>
where
T: Ord,
{
fn priority_insert(&mut self, v: T) {
self.insert(find_position(self, &v), v);
}
}

The only thing left is the implementation of find_position. As said, this is a binary search but its implementation is a little tricky (algebraic in fact) because we need to deal carefully with many cases:

fn find_position<T>(q: &VecDeque<T>, v: &T) -> usize
where
T: Ord,
{
if q.is_empty() {
return 0;
}

let (mut a, mut b) = (0usize, q.len() - 1);

// check v < a
if…

--

--

applied.math.coding

I am a Software Developer - Rust, Java, Python, TypeScript, SQL - with strong interest doing research in pure and applied Mathematics.