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

My book Essential Algorithms: A Practical Approach to Computer Algorithms describes lots of other interesting data structures and algorithms, many just as interesting but less complicated than this one. For more information about queues, priority queues, trees and other algorithmic topics, give it a look.

The first part of this post, Make an efficient priority queue class in C#, Part 1, explains how to use a heap data structure to build a priority queue that can add items in O(log N) steps. This post explain how to use the heap to remove items in O(log N) time.

How It Works

Because the values are stored in a heap, it's easy to find the item with the highest priority: it's sitting at the top of the heap. That means you can return it in 1 step.

Unfortunately if you remove the top node from the heap, it's no longer a heap. In fact it isn't even a tree. To keep the queue working, you need to fix the heap.

One way to do that is to move the last item in the tree to the root node. Then at least you have a tree again. Unfortunately the last item is almost guaranteed to not have the highest priority, so the tree is no longer a heap. Now you need to fix the heap.

To do that, you compare the current node (initially the root) with its children. If it has a higher priority than both children, then the heap property is satisfied here so the tree is once again a heap and you're done.

If the current node has a smaller priority than one of its children, you swap the current node and the larger child. Because the larger child has a higher priority than the smaller child, you know the heap property is now satisfied at this point. Next you move down into the child node that you swapped and repeat.

You continue moving down the tree until you reach a leaf node or you come to a point where the heap property is already satisfied.

An Example

For an example, consider the heap shown in Figure 1. The item with the highest priority is sitting at the top with value 50. We remove that item and replace it with the last item as shown in Figure 2.

Removing the top item takes only 1 step. The post Map between nodes and node numbers in a binary tree in C# explains how you can find the last item (with priority 8) in the tree in O(log N) time. Then swapping the last item to the top of the tree only takes a few steps so the total time so far is O(log N).

After swapping the last item to the top of the tree, we compare it to its children. The value 8 is less than 41 and 25, so we swap that node with its larger child as shown in Figure 3.

Now you again compare the priority of the item that you moved down (8) to the priorities of its children (22 and 34). The value 8 is smaller than the priorities of one of the children so you swap it with the larger, in this case 34, as shown in Figure 4.

Once again you compare the priority of the item that you're moving down (8) to the priorities of its children (now 10 and 29). The value 8 is smaller than the children so you swap it with the larger, in this case 29, as shown in Figure 5.

At this point we've reached a leaf node so we're done. You can verify in Figure 5 that the tree is again a heap.

A Second Example

For a second example, suppose you start with the heap shown in Figure 5 and remove another item. This time you extract the top value 41 and replace it with the last value in the tree, which is 13. Figure 6 shows the sequence of swaps you then need to make.

At this point the moving node has priority 13, which is larger than the priorities of is children, 10 and 8. That means the heap property is satisfied at this point. Because we haven't rearranged any nodes in the child subtrees, they still satisfy the heap property. That means the tree is once again a heap and we're done without going all the way to the bottom of the tree.

The total time to remove the top item and fix the heap is:

• 1 step to remove the top node
• O(log N) steps to find the bottom node
• O(1) steps to swap the bottom value to the root
• O(log N) steps to push the swapped value down into the tree to rebuild the heap

That makes the total run time O(log N).

C# Code

The following code shows the HeapQueue class's Dequeue method. It's a bit long but fairly simple.

// Remove the item with the largest priority from the queue. public void Dequeue(out T top_value, out int top_priority) { // Make sure the heap isn't empty. if (_NumItems < 1) throw new Exception("The queue is empty"); // Save the return values. top_value = Root.Data; top_priority = Root.Priority; _NumItems--; // If the heap has only one node, empty it. if (_NumItems == 0) { Root = null; return; } // Find the parent of the last node. DataNode parent = Root.FindNodeParentByNumber(_NumItems); // Find the last node. DataNode last_node; if (parent.RightChild != null) { last_node = parent.RightChild; parent.RightChild = null; } else { last_node = parent.LeftChild; parent.LeftChild = null; } // Copy the last node's values to the root. Root.Data = last_node.Data; Root.Priority = last_node.Priority; // Push the data down through the tree. DataNode node = Root; while (node != null) { // See if node is bigger than its children. // Get the child priorities. int left_priority = int.MinValue; if (node.LeftChild != null) left_priority = node.LeftChild.Priority; int right_priority = int.MinValue; if (node.RightChild != null) right_priority = node.RightChild.Priority; // If the node has higher priority than its children, // then the tree is again a heap and we're done. if ((node.Priority > left_priority) && (node.Priority > right_priority)) break; // Swap the node with its larger child. if (left_priority > right_priority) { // Swap with the left child. SwapNodes(node, node.LeftChild); // Move down to the left child. node = node.LeftChild; } else { // Swap with the right child. SwapNodes(node, node.RightChild); // Move down to the right child. node = node.RightChild; } } }

The method starts by checking some special cases. First it checks that the queue isn't empty and throws an exception if it is.

Next it saves the top data value and priority so it can return them later.

If the queue is now empty, the method sets the root node to null and returns.

Now that it's finished with the special cases, the method implements the algorithm described above. It calls FindNodeParentByNumber to find the parent node of the last node in the tree. It then finds the last node itself and removes it from the parent node. It then copies the last node's values into the root node.

Next the code enters a loop that runs while it is pushing the swapped value down into the tree. Each time through the loop, the code compares the node's priority to those of its children. If the node's priority is greater, the code breaks out of the loop.

Note that the code treats missing children as if they have the same priority as the moving node. Then when the code reaches a leaf node, it breaks out of the loop.

If the node's priority is lower than those of its children, the code swaps the node's data and priority of with the higher priority child node and then continues the loop to move farther down the tree.

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.