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

}

`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…