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

}