BlackWaspTM

This web site uses cookies. By using the site you accept the cookie policy.This message is for compliance with the UK ICO law.

Algorithms and Data Structures
.NET 3.5+

A Generic Priority Queue

A queue is a data structure that preserves the order of items added to it to give first in, first out, or FIFO, operation. A priority queue is similar but attaches a priority to each element, so that the more important items are extracted earlier.

Priority Queues

Queues are data structures to which you can add items and later extract them in their original order. This leads to the name, "first in, first out" queue, or FIFO, as the first item added to the queue will be the first that is received from it.

Queues have many uses in software development. For example, imagine that you are developing a service that must process messages in the correct order, and that service can occasionally receive messages more quickly than they can be processed. A solution to this problem is to enqueue the messages as they arrive and process items from the front of the queue. This throttles the message flow and makes the processing of messages asynchronous with respect to the software that generates them.

A priority queue is a special type of queue. Each item added to the queue has an associated priority. In general, the FIFO nature is maintained but high priority items can "jump" the queue and be processed ahead of lower priority elements. Every time you dequeue an item you know that it will be of the highest priority. However, items that are of the same priority are always dequeued in the order in which they were enqueued.

The .NET framework does include an implementation of a generic priority queue. However, it is internal so cannot be instantiated without using reflection. Internal items should not be used, as there is no guarantee that they will continue to operate in the same manner when the .NET framework is updated. Rather than use the internal class, we'll create our own.

PriorityQueue<T>

To begin, create a new project and add a class named, "PriorityQueue". We'll be creating a generic class that has two type parameters. The first specifies the type of the priority variable. This will allow us to use any type for the priority, as long as we can compare two values to determine which is the more important. The second type parameter will be used to specify the type of the items in the queue.

public class PriorityQueue<TPriority, TItem>
{
}

Adding the Queue Storage

We could use a heap to store the items in the queue, organising the heap so that the highest priority item is always at the top. However, rather than implement this, we'll use some of the built-in .NET framework types. We'll hold the items in a set of queues with each queue storing values of the same priority.

The individual queues will be held in a SortedDictionary. This type of dictionary is automatically sorted in the order of its keys. Each key/value pair will hold the priority in the key and a queue of items in the value. We'll start with an empty dictionary and add queues only when a new priority value is provided. When one of the subqueues becomes empty, we'll remove it from the overall data structure.

Add the following field to the PriorityQueue class to hold the set of queues.

readonly SortedDictionary<TPriority, Queue<TItem>> _subqueues;

Constructors

The SortedDictionary must be initialised in the constructor, as it is set to be read only. The class has two constructors. The first has a parameter that allows you to specify a comparer that can be used to determine which of two priorities is the more important. The second constructor omits the comparer, instead using the default comparer for the priority type.

public PriorityQueue(IComparer<TPriority> priorityComparer)
{
    _subqueues = new SortedDictionary<TPriority, Queue<TItem>>(priorityComparer);
}

public PriorityQueue() : this(Comparer<TPriority>.Default) { }

HasItems and Count Properties

Let's add two properties to the class. The first, HasItems returns a Boolean value, which will be true if the queue has at least one item and false if the queue is empty. This will be useful for consumers of the class but is also used internally. We can determine if there are any items by checking if the SortedDictionary contains any queues.

public bool HasItems
{
    get { return _subqueues.Any(); }
}

The Count property returns the total number of items in the priority queue, calculated by summing the Count values of each subqueue.

public int Count
{
    get { return _subqueues.Sum(q => q.Value.Count); }
}
11 February 2013