A priority queue is a queue data structure where the element with the lowest (or highest) value is always at the front. A common analogy is to think of a queue of people ordered by some criteria such as age or height. Many programming languages include a priority queue in their standard library, including C++ and Java. However, the Microsoft .Net Framework does not include a priority queue, which is why I provide one here.

You might wonder why you can’t just use a sorted list to get the same effect as a priority queue. And the answer is, you can. A sorted list is a perfectly valid way to implement a priority queue. However, with a priority queue we are only interest in the smallest element at any time, and not any of the other elements, which means it is not necessary to maintain a total order of all the elements. Because of this, we can use an implementation that maintains only a partial order, which can provide better performance.

The most common such implementation is one that uses a binary heap. A binary heap is a binary tree with the property that any element in the tree is always smaller than both of its children. This guarantees that the smallest element is always on top, although the binary heap does not maintain a total order like a binary search tree. Efficient operations exist to maintain this heap property when inserting and deleting elements, making the binary heap perform better for priority queues than a sorted list. My PriorityQueue class for .Net uses a binary heap implementation.

The PriorityQueue<T> generic class that I provide here is written to conform to the conventions used by .Net’s built-in collection classes in the System.Collections.Generic namespace, particularly the Queue<T> class. The PriorityQueue<T> class implements IEnumerable<T> and ICollection.

The three main operations provided are Enqueue, which adds an item to the queue; Dequeue, which removes and returns the first element of the queue; and Peek, which returns the first element without removing it. In this implementation, these operations are O(log n), O(log n) and O(1) respectively. A special operation, AdjustFirstItem, allows you to change the value of the first item and re-evaluate its position in the queue, in less time than it would’ve taken to remove the element and add a new one (note that this is only possible with reference types that are not immutable).

The PriorityQueue<T> class provides several constructors, including one that allows you to create a priority queue from an existing list of elements with O(n) time complexity, faster than individually adding each element to the list with Enqueue.

You can put any type of element in the priority queue as long as it implements IComparable<T>, or you provide a custom IComparer<T> for the type. Note that the PriorityQueue<T> class will always put the smallest element at the front. If you want to have the largest element at the front, you can use the included InvertedComparer<T> class.

A short example of how to use the PriorityQueue<T> class is provided below.

PriorityQueue<int> queue = new PriorityQueue<int>(new[] { 4, 7, 3, 9, 12 }); // create a priority queue with the specified elements.
int n = queue.Dequeue(); // returns and removes 3; the front element is now 4.
queue.Enqueue(5); // the front element is still 4.
queue.Enqueue(2); // the front element is now 2.
n = queue.Peek(); // returns 2, but does not remove it.

Download the PriorityQueue<T> class for .Net (class library, sample application, and source code provided).

Read the documentation for the PriorityQueue<T> class.

Categories: Programming
Posted on: 2009-04-29 06:17 UTC.