Immutable Priority Queues
Two Dual 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 DualItemImmutablePriorityQueue<T>.

Before you ask … no, we’re not going to create separate implementations for every possible size of queue. A heap structure, such as the one shown here, contains three different situations we need to accommodate:

• Leaf nodes with no children (green, implemented by SingleItemImmutablePriorityQueue);
• Interior nodes with exactly one child (orange, implemented by DualItemImmutablePriorityQueue);
• Interior nodes with exactly two children (blue, implemented by BranchingImmutablePriorityQueue).

Leaf nodes are represented by the SingleItemImmutablePriorityQueue<T> we defined earlier; interior nodes with one child will be represented by the DualItemImmutablePriorityQueue<T> discussed today; we’ll finish off next time with the BranchingImmutablePriorityQueue<T> class.

Remember that our priority queue is defined by a delegate that ranks our items; this dual item queue is the first time we’ll be making use of it.

public sealed class DualItemImmutablePriorityQueue<T>
    : IImmutablePriorityQueue<T>
{
    private readonly SingleItemImmutablePriorityQueue<T> _rest;
    private readonly Comparison<T> _comparer;

We don’t define _rest as an IImmutablePriorityQueue<T> because we really don’t want to have nodes with a single child in the middle of our heap - this would allow the tree to become unbalanced or degenerate, leading to poor performance characteristics. We instead only support these appearing at the edges of the heap.

    internal DualitemImmutablePriorityQueue(
        T head,
        SingleItemImmutablePriorityQueue<T> rest,
        Comparison<T> comparer)
    {
        if (rest == null)
        {
            throw new ArgumentNullException(nameof(rest));
        }

        _comparer = comparer ?? throw new ArgumentNullException(nameof(comparer));

After we’re done initializing our members, we need to work out which of our two items should be at the front of the queue.

        if (_comparer(head, rest.Head) < 0)
        {
            Head = head;
            _rest = rest;
        }
        else
        {
            Head = rest.Head;
            _rest = new SingleItemImmutablePriorityQueue<T>(head, _comparer);
        }
    }

Next, we have our member properties, with definitions that should be pretty obvious …

    public T Head { get; }
    public int Count => 2;
    public int Height => 2;
    public bool IsEmpty => false;

When we want to enqueue an item into our queue, we return a BranchingImmutablePriorityQueue<T>. But, before we can construct it, we need to identify whether our existing Head goes at the top or the value we’ve just been given.

    public IImmutablePriorityQueue<T> Enqueue(T value)
    {
        if (_comparer(Head, value) < 0)
        {
            return new BranchingImmutablePriorityQueue<T>(
                Head,
                new SingleItemImmutablePriorityQueue<T>(value, _comparer),
                _rest,
                _comparer);
        }

        return new BranchingImmutablePriorityQueue<T>(
            value,
            new SingleItemImmutablePriorityQueue<T>(Head, _comparer),
            _rest,
            _comparer);
    }

Notice that we’re not comparing the two branches of the queue here. We’re relying on the constructor of the branching queue to keep those organized with the higher priority on the left.

Finally, dequeuing our Head is very simple - we just return the single item queue stored in _rest.

    public IImmutablePriorityQueue<T> Dequeue() => _rest;
}

An Alternative Approach

Instead of storing a SingleItemImmutablePriorityQueue<T> for the _rest of the queue, we could just store the item directly. Let’s explore the differences this would make to our class.

public sealed class DualitemImmutablePriorityQueue<T> 
    : IImmutablePriorityQueue<T>
{

The member _rest becomes a simple field containing the item.

    private readonly T _rest;
    private readonly Comparison<T> _comparer;

The constructor now accepts the value directly. When we compare the two values, we no longer need to create a SingleItemPriorityQueue<T> in the case where they need to be swapped.

    internal DualitemImmutablePriorityQueueAlternate(
        T head,
        T rest,
        Comparison<T> comparer)
    {
        _comparer = comparer ?? throw new ArgumentNullException(nameof(comparer));

        if (_comparer(head, rest) < 0)
        {
            Head = head;
            _rest = rest;
        }
        else
        {
            Head = rest;
            _rest = head;
        }
    }

    public T Head { get; }
    public int Count => 2;
    public int Height => 2;
    public bool IsEmpty => false;

When we enqueue a new item, we need to create a SingleItemImmutablePriorityQueue<T> to wrap both items, since we don’t have one available.

    public IImmutablePriorityQueue<T> Enqueue(T value)
    {
        if (_comparer(Head, value) < 0)
        {
            return new BranchingImmutablePriorityQueue<T>(
                Head,
                new SingleItemImmutablePriorityQueue<T>(value, _comparer),
                new SingleItemImmutablePriorityQueue<T>(_rest, _comparer),
                _comparer);
        }

        return new BranchingImmutablePriorityQueue<T>(
            value,
            new SingleItemImmutablePriorityQueue<T>(Head, _comparer),
            new SingleItemImmutablePriorityQueue<T>(_rest, _comparer),
            _comparer);
    }

Lastly, when we dequeue the head, we need to create a SingleItemImmutablePriorityQueue<T> to wrap _rest.

    public IImmutablePriorityQueue<T> Dequeue() 
        => new SingleItemImmutablePriorityQueue<T>(_rest, _comparer);
}

It’s interesting to compare these two implementations. The later one reduces the overall footprint of the queue, but at the cost of slightly higher object churn overall. I suspect the impact of this would depend on the lifetime of the queue - whether the queue is short lived or not - due to the impact on garbage collection generations.