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
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.
PriorityQueue class implements the
ICollection interface from the
System.Collections namespace. In addition, it has the following methods:
Enqueue - Adds an element to the
Dequeue - Removes the element from the head of the
Remove - Removes the specified element from the
Contains - Returns a value indicating whether the specified element is contained in the
Peek - Returns the first element in the
PriorityQueue without removing it.
Clear - Removes all of the elements from the
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()
if(Count == 0)
throw new InvalidOperationException(
"Cannot dequeue into an empty PriorityQueue.");
object element = header.Element;
Node oldNode = header;
for(int i = 0; i < currentLevel && header[i] == oldNode; i++)
header[i] = oldNode[i];
while(currentLevel > 1 && header[currentLevel - 1] == null)
Debug.Assert(count >= 0);
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 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.
PriorityQueue orders the elements in descending order. What this means is that if the result of a comparison using either
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
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.
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!
- 03/03/2006 - First version posted.
- 03/11/2006 - Fixed bug in the