Following on from my 2016/2017 series on immutable types, this short series explores the implementation of an immutable priority queue.

What is a priority queue?

A regular queue preserves the order of items - they are removed from the end of the queue in the same sequence that they were admitted to the queue originally.

By introducing an ordering function, a priority queue reorders items so that the most important items are removed from the queue first. Effectively, some items are fast-tracked and reach the front of the queue quickly, while others are held aside for later.

Introducing the Priority Queue

Saturday, October 20 2018 priority-queues csharp

Recently, while working on a personal project, I needed a priority queue. Instead of slamming all of the items into a sorted list and making do, I decided to do the job properly and write a proper abstraction. To keep things interesting, it was an immutable implementation.

Read more »

Designing the External API

Saturday, October 27 2018 priority-queues csharp

As we did previously with our regular immutable queue, we should start by considering the design of our external interface - our API. How do we want our users to create and interact with our priority queue?

Read more »

Dequeuing Values

Saturday, November 03 2018 priority-queues csharp

Before we can start on the actual implementation of our immutable priority queue, we need to understand the algorithms we’re going to use. There are two different scenarios to consider - when we enqueue something onto the queue, and when we dequeue the head.

Read more »

Enqueuing Values

Saturday, November 10 2018 priority-queues csharp

After exploring last time how to remove an item from a queue, let’s look at the slightly more complex case of adding items.

Read more »

Simple Queues

Saturday, November 17 2018 priority-queues csharp

As we did with our original immutable queue, we’ll define dedicated implementations of IImmutablePriorityQueue<T> for handling empty and single item queues.

Read more »

Two Dual Item Queues

Saturday, November 24 2018 priority-queues csharp

Once we have a priority queue containing a single item, how do we handle enqueuing the next item onto the queue? The answer, of course, is buried in the code from from last time: we introduce the DualItemImmutablePriorityQueue<T>.

Read more »

Creating Branching Nodes

Saturday, December 01 2018 priority-queues csharp

For a queue exceeding two items, our existing implementations are insufficient. We need another - a BranchingImmutablePriorityQueue<T>. Each of these nodes will combine two existing sub-queues with a head item to form a tree structure.

Read more »

Queue Testing

Saturday, December 08 2018 priority-queues csharp

It’s vital that our priority queue returns items in the correct order, so we should write some unit tests to ensure that items are returned in the order desired. Fortunately, we can test this fairly easy using property tests.

Read more »