Immutable Priority Queues
Designing the External API

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?

Let’s begin with an interface declaration to define how to interact with a priority queue once created:

public interface IImmutablePriorityQueue<T>
{
    // The item at the front of the queue
    T Head { get; }

    // Test to see if the queue is currently empty
    bool IsEmpty { get; }

    // Count of items contained in the queue
    int Count { get; }
    
    // Add an item into the queue
    IImmutablePriorityQueue<T> Enqueue(T value);

    // Discard the front item from the queue
    IImmutablePriorityQueue<T> Dequeue();
}

You might observe that this is very close to the declaration of IImmutableQueue that we’ve previously explored. The primary difference is the inclusion of Count, which we need later on to keep our queue internally balanced.

To create an empty priority queue, we’ll follow the pattern already used by other immutable types in .NET and create a factory method:

public class ImmutablePriorityQueue<T>
{
    public static IImmutablePriorityQueue<T> Create(
        Comparison<T> comparer)
        => new EmptyImmutablePriorityQueue<T>(comparer);
}

Unlike some other immutable types, our empty queues need a little configuration in the form of a the comparer parameter. This uses one of the standard .NET delegate types, Comparison<T>, allowing users to pass a comparison function or delegate of their choice to control how the priority queue orders items.

For convenience of our users, we should supply some alternative approaches for users to specify the priority of each item. Doing this makes it easier for our consumers to get the effect they want.

If our user already has an implementation of IComparer<T> that they want to use, we can use its Compare method as the comparison delegate:

public static IImmutablePriorityQueue<T> Create(IComparer<T> comparer)
    => new EmptyImmutablePriorityQueue<T>(comparer.Compare);

If the items going into the queue are already naturally ordered in the desired sequence (e.g. classes like int or string that already implement IComparable<T>), we can create the delegate ourselves:

public static IImmutablePriorityQueue<TItem> Create<Item>()
    where Item : T, IComparable<T>
{
    int Comparer(TItem left, TItem right) => left.CompareTo(right);
    return new EmptyImmutablePriorityQueue<TItem>(Comparer);
}

When there’s already a property on our items that can be used to order, such as when we’re ordering cars by total distance travelled, we should allow users to specify a key value to use:

public static IImmutablePriorityQueue<T> Create<Key>(
    Func<T, Key> keySelector)
    where Key : IComparable<Key>
{
    if (keySelector is null)
    {
        throw new ArgumentNullException(nameof(keySelector));
    }

    int Compare(T left, T right)
    {
        var leftKey = keySelector(left);
        var rightKey = keySelector(right);
        return leftKey.CompareTo(rightKey);
    }

    return new EmptyImmutablePriorityQueue<T>(Compare);
}

Note how we’ve used a local function to make it easier to read the code; I think this is better than writing a complicated delegate directly within the Create() call.

With these four ways to create an empty priority queue, it should be easy for our users to get started without having to jump through any nasty hoops. Of course, before that can happen, we need to implement the actual queue ourselves.