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.
After exploring last time how to remove an item from a queue, let’s look at the slightly more complex case of adding items.
As we did with our original immutable queue, we’ll define dedicated implementations of
IImmutablePriorityQueue<T> for handling empty and single item queues.
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