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).

2009-04-29 11:02 UTC

A good priority queue is a valueble asset with asynchronous development, thanks for this Sven.

I really appriciate it!

2009-04-30 12:46 UTC

Once again, top notch stuff Sven.

2009-05-13 15:41 UTC

Can it hold multiple objects with same priority.

(1, A)

(1, B)

(1,D)

(2, H)

(3, N)

etc

2009-05-14 01:39 UTC

Yes, but it does not guarantee any particular ordering between those objects.

2009-11-03 08:23 UTC

Excellent library. I needed an IEnumerable PriorityQueue, for a CPU process scheduling simulator. This was exactly what I needed. Thanks!

Comments are closed for this post. Sorry.

- Comments are now closed
- .Net Configuration Section Documentation Generator
- Creating a route for a .asmx Web Service with ASP.NET routing
- Welcome to the new Ookii.org
- Ookii.CommandLine 2.2
- Floppy support in Windows Virtual PC 7
- Singapore
- FormatC 2.0 (syntax highlighting) now available
- Opening files via IDropTarget in .Net
- Command line argument parser for .Net