A Priority Queue in C#

• Download source files - 4.56 Kb

Introduction

Recently, I was creating a state machine in which I needed time-stamped events. Rather than just a simple clock tick, I needed timed events with their own IDs so that I could distinguish one event from another. Researching this problem led me to the idea of using a priority queue. I could enqueue the timed events along with their information in any order; the priority queue would take care of ordering the events properly. A timer would periodically check the priority queue to see if it is time for the event at the head of the queue to fire. If so, it dequeues the event and invokes the delegate associated with it. This approach was exactly what I was looking for.

Searching here at CodeProject, I found that a priority queue[^] class had already been written. However, it occurred to me that I could easily write my own using my old friend, the skip list. This would have the advantage that the dequeue operation would only take O(1) time, while the enqueue operation would still be log(n) on average. I thought that using skip lists in this way was novel enough that it merits its own article. So here it is. I hope you find it interesting.

Skip Lists as Priority Queues

I'll refer you to my skip list[^] article for a description of them. What I want to concentrate on in this article is how to use them to implement priority queues and my PriorityQueue class.

Below is an illustration of a skip list as a priority queue before a dequeue operation. Since a skip list is made up of a series of nodes connected one after the other, removing an item from the front of the list is just a matter of removing the first node:

The arrow points to the first item in the list. Notice that it points to the first node after the header. The header node is always present in a skip list regardless of whether there are any other nodes in the list and does not actually hold an item; it's there to mark the beginning of the list, and is used as the starting point for traversing it.

Also notice that the items are in descending order. Since this is a priority queue, the items are ordered from greater to lesser values. There may be times, however, when you want items in ascending order, i.e., lower values have greater priorities than higher values. I'll discuss how to achieve this with my PriorityQueue class, later. But I'm getting ahead of myself.

Next, we see that the previous head of the list has been removed, and that, what was the second item in the list has now become the first item in the list. Since removing the first node (after the header) does not affect the nodes that come after it, no rebalancing is necessary. We do have to update the header so that its pointers, up to the level of the node that was removed, now point to the node that comes after it. This takes very little time.

The PriorityQueue Class

When I decided to use a skip list for implementing a priority queue, my first thought was to reuse my SkipList[^] class. However, I wanted to optimize the dequeue operation, so I decided to rewrite the algorithms from scratch for my new PriorityQueue class. Fortunately, the skip list algorithms are so simple that this can be done quickly and easily.

The PriorityQueue class implements the ICollection interface from the System.Collections namespace. In addition, it has the following methods:

• Enqueue - Adds an element to the PriorityQueue.
• Dequeue - Removes the element from the head of the PriorityQueue.
• Remove - Removes the specified element from the PriorityQueue.
• Contains - Returns a value indicating whether the specified element is contained in the PriorityQueue.
• Peek - Returns the first element in the PriorityQueue without removing it.
• Clear - Removes all of the elements from the PriorityQueue.

The methods are pretty much straightforward implementations of the skip list algorithms. The Dequeue algorithm is what makes the skip list especially useful as a priority queue, so I'll talk about how it is implemented:

public virtual object Dequeue()
{
    #region Require

    if(Count == 0)
    {
        throw new InvalidOperationException(
            "Cannot dequeue into an empty PriorityQueue.");
    }

    #endregion

    // Get the first item in the queue.

    object element = header[0].Element;

    // Keep track of the node that is about to be removed.

    Node oldNode = header[0];

    // Update the header so that its pointers that pointed to the

    // node to be removed now point to the node that comes after it.

    for(int i = 0; i < currentLevel && header[i] == oldNode; i++)
    {
        header[i] = oldNode[i];
    }

    // Update the current level of the list in case the node that

    // was removed had the highest level.

    while(currentLevel > 1 && header[currentLevel - 1] == null)
    {
        currentLevel--;
    }

    // Keep track of how many items are in the queue.

    count--;

    version++;

    #region Ensure

    Debug.Assert(count >= 0);

    #endregion

    #region Invariant

    AssertValid();

    #endregion

    return element;
}

From top to bottom:

• Test the preconditions. I put this in its own region to mark it off from the rest of the code. I called the region "Require" with a tip of the hat to the Eiffel programming language. The precondition for the dequeue operation is that the priority queue must not be empty. An exception will be thrown when an attempt is made to dequeue an empty priority queue.
• Get the first element in the list. The nodes in this list are represented by a private Node class. This class implements an indexer that gives you access to its "forward" pointers, or references, to the next nodes in the list. To get the first element, we access the node the header points to at the lowest level, zero. This element will be returned at the end of the dequeue operation.
• Keep track of the node about to be removed. We need this so that we can update the header, which comes next.
• Update the header so that its pointers that pointed to the node being removed now point to the node that comes after it.
• Update the current level of the list. It's possible that the node that was removed had the highest level in the list. If so, we need to update the list level.
• Update the list count.
• Update the PriorityQueue version. When a PriorityQueue enumerator is created, it stores the PriorityQueue's version. When an operation, such as MoveNext, is performed, the enumerator will compare its stored version with the current PriorityQueue version to make sure that the PriorityQueue has not changed. In theory, this could cause problems if the version value rolls all the way over before the enumerator checks. This seems highly unlikely, however.
• The next region is the "Ensure" region. It checks the post-conditions. Here, I just check to make sure that the count is non-negative. A more robust implementation might store the old count value and make sure that the new count value was the old count minus one. But that seems to me as overkill here.
• Next, the "Invariant" region. It calls an AssertValid method. This method is only compiled in the debug version. It tests to makes sure none of the PriorityQueue's invariants have been violated.
• Finally, return the element that was at the head of the PriorityQueue.

The PriorityQueue class provides two constructors, a default one, and one that takes an IComparer object. If the default constructor is used, the PriorityQueue will cast its elements to the IComparable interface in order to compare them to determine their priority and order in the list. This assumes, of course, that if the default constructor is used, the elements that are enqueued into the PriorityQueue implement the IComparable interface. If not, an exception will be thrown when an attempt is made to compare the elements. If the IComparer constructor is used, the PriorityQueue will use the specified IComparer object for comparing elements.

The PriorityQueue orders the elements in descending order. What this means is that if the result of a comparison using either IComparable or IComparer is greater than zero, it will order that element before the one it is comparing it to. If you need the elements in ascending order, your IComparable or IComparer object will need to return a value greater than zero when one element is less than the element it is being compared to, and less than zero when one element is greater than the element is it compared to. Also, duplicates are allowed. If two elements are equal, the element being enqueued into the PriorityQueue will be inserted before the element already in the queue.

Conclusion

This experience has renewed my admiration for the skip list data structure. It is truly neat. I hope you find this class helpful, and as always, comments and suggestions are appreciated and welcomed. Thanks!

History

• 03/03/2006 - First version posted.
• 03/11/2006 - Fixed bug in the Contains method.