Title: Make an efficient priority queue class in C#, Part 1

For more information about queues, priority queues, trees and other algorithmic topics, see my book Essential Algorithms: A Practical Approach to Computer Algorithms.

A priority queue is a data structure that holds data values with associated priorities. The Enqueue method adds a new item to the queue. The Dequeue method removes the item in the queue that has the highest priority. This example shows how to build a priority queue that lets you add and remove items very quickly. Before I explain how the queue works, I want to discuss the performance of two other kinds of priority queues.

List Queue

The post Make a generic priority queue class in C# uses two lists to hold data and priorities.

Its Enqueue method simply adds a new data and priority to the lists. The List class used by the .NET Framework stores values in an array so adding a new item may cause the array to resize, which could take some time. Let's assume the array resizes in huge chunks so it won't need to resize again and we can ignore the time it takes to add a new item. That means if the queue holds N items, then adding a new item to the queue takes O(1) time.

The previous example's Dequeue method looks through the list of priorities to find the one with the largest priority. It then removes and returns that item. If the queue currently holds N items, finding the one with the largest priority takes O(N) steps. If the items are stored in a list (which internally keeps the items in an array), then removing the item requires the list to compact the remaining entries, which will take O(N) steps. That means removing an item from the queue will take O(N) steps.

Linked List Queue

Instead of storing items and priorities in List objects, the queue could store values in linked lists. (See my book for information on linked lists).

In that case adding an item to the queue would require only 1 step with no array resizing necessary.

Removing an item from the queue would take O(N) steps to search the list for the item with the highest priority. It would then take only 1 step to remove the item, so the total time for the Dequeue method would be O(N).

A More Efficient Queue

You can build a more efficient priority queue by storing items in a heap. A heap is a special kind of binary tree structure where every node has value (in this case priority) greater than the values of its two children. The heap also has all of its leaf nodes on the bottom two levels and pushed as far to the left as possible. Basically it's the shortest tree that can hold the number of nodes it contains.

For example, Figure 1 shows a heap. You can look at the figure to verify that each node has a value larger than the values of its children and that all of the leaf nodes are in the bottom left of the tree.

Notice that the heap property doesn't say anything about the ordering of a node's siblings. For example, the root node has value 50 which is greater than the values of its children: 41 and 25. The heap property doesn't say the smaller child must be on the left. If it did, then the tree would be completely sorted, which is a stronger requirement than the heap property.

Also notice that the leaf nodes are on the bottom two levels and pushed to the left.

It turns out that you can use a heap to build an efficient priority queue. Instead of requiring O(1) time to enqueue items and O(N) time to dequeue items, a heap lets you enqueue and dequeue in O(log N) time.

Enqueue

To enqueue an item, you first add it to the bottom of the tree. For example, suppose you want to add an item with priority 30 to the tree shown in Figure 1. You first add it at the bottom as shown in Figure 2.

Unfortunately that violates the heap property because the new value, 30, is greater than the value in the new node's parent, 4. Fortunately it's easy to fix the heap property at this node by swapping the values of this node and its parent as shown in Figure 3.

Of course that violates the heap property at the new node because its value, 30, is greater than its new parent, 25. To fix that, you just swap the node with its parent again as shown in Figure 4.

It is important to note that when you swap a node the heap property is satisfied at that point for both of the node's new children. For example, in Figure 4 the new value 30 is greater than its two child values 20 and 25. You know the value is greater than value of the child that was just swapped (25) because that was the reason you swapped them.

You also know that the swapped child (node 25) was the parent of the node's other child (node 20) so you know it was greater (25 > 20). Because the value you swapped up is greater than the first child (25), it must also be greater than the other child (because 30 > 25 > 20).

Because the value you swapped up must be greater than the values of its two new children, the heap property is satisfied at this node.

You continue swapping the new value up the tree until either it reaches the top or its parent has a larger value. At that point the tree is a heap once again.

In Figure 4 the new value (30) is smaller than its parent's value (50) so we're done and the tree is a heap again.

If the heap holds N values, then it has height O(log N) so it will take at most O(log N) steps to swap the new value from the bottom of the tree to its final position.

C# Code

The example program uses a DataNode class to hold information about a value. It has properties Data, Priority, LeftChild, RightChild, and Parent.

The HeapQueue class builds a heap from DataNode objects.

The following code shows the HeapQueue class's Enqueue method.

// Add an item to the queue. public void Enqueue(T new_value, int new_priority) { // Make the new data node. DataNode child = new DataNode(new_value, new_priority); // If the heap is empty, create it. if (Root == null) { Root = child; _NumItems = 1; return; } // Get the new node's number. int new_node_number = _NumItems++; // Find the parent of the new node. DataNode parent = Root.FindNodeParentByNumber(new_node_number); // Add the new node to the parent. if (parent.LeftChild == null) parent.LeftChild = child; else parent.RightChild = child; // Swap the new node up to the root fixing the heap. while (child.Parent != null) { // If the parent's priority is bigger, // the heap is fixed so we're done. if (child.Priority <= child.Parent.Priority) break; // Swap the new node and its parent. SwapNodes(parent, child); // Move up. child = parent; parent = child.Parent; } }

The method first creates a new DataNode object to hold the new entry.

If the heap is empty, the method makes the root node refer to the new node and it is done.

If the heap isn't empty, the method calls the DataNode class's FindNodeParentByNumber method to find the node that should be the parent of the new node. In Figure 1 that would be the node 4 because we will add the new value below that node. Download the example and look at the code to see how the FindNodeParentByNumber method works.

After it has the node's parent, it sets the parent's LeftChild or RightChild property to refer to the new node.

The method then enters a loop that runs until the tree is a heap again. The loop's while condition makes it end if the new value reaches the root node.

Inside the loop, if the new node's priority is less than or equal to the priority of its parent, then the tree is a heap so the program breaks out of the loop.

If the new node's value is greater than that of its parent, the code calls the SwapNodes method to swap the node values and it continues up the tree.

The following code shows the SwapNodes method.

// Swap the contents of two DataNode objects. private void SwapNodes(DataNode node1, DataNode node2) { T temp_data = node1.Data; int temp_priority = node1.Priority; node1.Data = node2.Data; node1.Priority = node2.Priority; node2.Data = temp_data; node2.Priority = temp_priority; }

This method simply swaps the data and priorities of the two nodes.

That's how the Enqueue method works. It took a lot of explanation but the method itself is pretty simple. In my next post I'll explain how the Dequeue method works.

Be sure to look at my book Essential Algorithms: A Practical Approach to Computer Algorithms for more information about other interesting and useful algorithms.

Download the example to experiment with it and to see additional details.