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
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
- Interior nodes with exactly one child (orange, implemented by
- Interior nodes with exactly two children (blue, implemented by
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
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.
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.
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.
Next, we have our member properties, with definitions that should be pretty obvious …
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.
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
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.
_rest becomes a simple field containing the item.
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.
When we enqueue a new item, we need to create a
SingleItemImmutablePriorityQueue<T> to wrap both items, since we don’t have one available.
Lastly, when we dequeue the head, we need to create a
SingleItemImmutablePriorityQueue<T> to wrap
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.