Priority Queue for .Net

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.

Comments

Matthijs Krempel

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!

Jason

2009-04-30 12:46 UTC

Once again, top notch stuff Sven.

Vijay

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

Sven Groot Author comment

2009-05-14 01:39 UTC

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

Jonathon Reinhart

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!

dot net training in chennai

2014-01-04 10:41 UTC

Good explanation with appropriate example.

Add comment

Latest posts

Categories

Archive

Syndication

RSS Subscribe