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.