Immutable Priority Queues
Creating Branching Nodes

For a queue exceeding two items, our existing implementations are insufficient. We need another - a BranchingImmutablePriorityQueue<T>. Each of these nodes will combine two existing sub-queues with a head item to form a tree structure.

Harking back to the introduction of this series, each of these nodes will need to satisfy some simple rules:

• The highest priority item should always be at the root of any subtree
• When there are two branches off a node, the higher priority item should be on the left

While the resulting tree is constrained by these rules throughout, we don’t need to worry about anything more than our current node when constructing the tree - we assume that any existing immutable priority queue already satisfies those rules.

The constructor for BranchingImmutablePriorityQueue<T> does the heavy lifting.

internal BranchingImmutablePriorityQueue(
    T head,
    IImmutablePriorityQueue<T> left,
    IImmutablePriorityQueue<T> right,
    Comparison<T> comparer)
{

We begin with our usual argument checking, ensuring that we don’t get any null values creeping in to cause mischief. When that’s complete, we initialize our private members and public properties.

    if (left is null)
    {
        throw new ArgumentNullException(nameof(left));
    }

    if (right is null)
    {
        throw new ArgumentNullException(nameof(right));
    }

    Head = head;
    Count = left.Count + right.Count + 1;
    _comparer = comparer 
        ?? throw new ArgumentNullException(nameof(comparer));

We need to apply our comparison delegate to ensure the two subtrees are correctly arranged, with the higher priority Head on the left.

    if (_comparer(left.Head, right.Head) <= 0)
    {
        // Highest priority Head is in `left`
        _left = left;
        _right = right;
    }
    else
    {
        // Highest priority Head is in `right`, so we swap them
        _left = right;
        _right = left;
    }

Finally, we do a check, comparing our head with the head of our left tree, to ensure that we have the highest priority value at the root. In normal operation, this check should be redundant, which is why we’ve done it as a debug assert statement.

    Debug.Assert(
        _comparer(head, _left.Head) <= 0, 
        "Expect Head to be prioritized over the lefthand branch.");
}

Combine this constructor with the enqueue and dequeue methods already discussed and we’re essentially complete.