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

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);
}