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.
It’s vital that our priority queue returns items in the correct order, so we should write some unit tests to ensure that items are returned in the order desired. Fortunately, we can test this fairly easy using property tests.
Sometimes our users might want to do something odd - like iterate the content of a queue without going to the hassle of dequeuing items one at a time. Fortunately, it’s not hard for us to support this.
I have a concern about the amount of debris created on the heap by the enumeration technique we used last time. Let’s explore an alternative approach and see how that compares.
As is always important, we need to implement hashing and equality. But what does equality mean for a queue?