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.
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.
We need to apply our comparison delegate to ensure the two subtrees are correctly arranged, with the higher priority
Head on the 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.