C# Priority Queue
Priority Queue
A C# Priority Queue is a specialized Queue data structure. The distinguishing trait of a Priority Queue is that elements with the highest/lowest priority are dequeued (returned) first. A regular queue on the other hand returns elements in the order they were inserted.
Our C# Priority Queue is written from scratch due to the inflexibility of the .NET Framework Queue class. The Priority Queue is implemented using an array-based Heap.
Heap
A heap data structure is binary tree that always preserves two properties:
The first property is that a Heap is always balanced. That is, nodes are always inserted in the next empty spot going down and going left to right. This makes sure that a heap is fast to search through.
The second property is that parent nodes are always smaller/bigger that children nodes. If a heap is a maxheap, the parent nodes must be bigger or equal to children nodes. If a heap is a minheap, the parent nodes must be smaller or equal.
Our particular C# Priority Queue is written with a min-heap. A slight modification is that the heap is array-based as opposed to linked-list based. All that means is that elements are stored within a List<> data structure.
The left child of any given cell inside the list is given by 2 * [the index of the cell]. while the right child is given by 2 * [the index] + 1.
Inserting to the Priority Queue
As mentioned above, the next empty spot in a Priority Queue is easy to figure out. Because our Priority Queue is array-based, any element can be inserted at the end of the list.
However in order to preserve the property of the Heap, the inserted item must be "bubbled up".
Bubble Up
Bubbling up a Priority Queue means swapping child nodes with parent nodes when they violate the heap-order property. For example, our Priority Queue uses a min-heap. If a child node's value is smaller than it's parent, then the parent and child are swapped.
Bubbling up starts at a node (usually the last one inserted) and compares the values going up towards the root of the heap.
Removing from the Priority Queue
Removing the top element in the Priority Queue means removing the root of the heap. To remove the root, the bottom right-most node is put in its place. The value of the root can then be returned to the programmer or user.
Since the node that is now the root might violate the heap-order property, it has to be "bubbled down".
Bubble Down
Bubbling down in a Priority Queue is similar to bubbling up. The difference is that it starts at a node and goes down towards the leaf nodes instead of up towards the root. The trick to remember is to swap the parent node with the smaller of the two children nodes.
Removing in the Middle
Removing a value that is not at the top of the Priority Queue is not supported in our C# Priority Queue class, but it can be done. The trick is to find the value node (or cell in our case), replace it with the bottom right-most node, and then bubble-up and bubble-down until the heap-order property is restored.
Conclusion
The .NET Framework does not come with a Priority Queue built-in. Our C# Priority Queue is pretty basic but it is a good base to build on. As a quick note, notice how inserting elements into a Priority Queue and then emptying the Priority Queue returns the elements in order. Congratulations, that is called Heap Sort and is very efficient.