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 »