.NET 3.5+

A Generic Priority Queue

by Richard Carr, published at http://www.blackwasp.co.uk/PriorityQueue.aspx

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.

Enqueue Method

We can now add the Enqueue method, which adds a new item to the queue. If a subqueue exists that contain items with the same priority as the new item, the new object is added to that queue. If not, a new queue is created and added to the dictionary first.

public void Enqueue(TPriority priority, TItem item)
{
    if (!_subqueues.ContainsKey(priority))
    {
        AddQueueOfPriority(priority);
    }

    _subqueues[priority].Enqueue(item);
}

The private AddQueueOfPriority method creates the new subqueue and adds it to the dictionary with the correct key.

private void AddQueueOfPriority(TPriority priority)
{
    _subqueues.Add(priority, new Queue<TItem>());
}

Dequeue Method

The Dequeue method removes an item from the top of the highest priority queue and returns it. We know that this item will be in the first queue in the dictionary so we can simply use this queue's Dequeue method to obtain the result. The only other possibility is that the priority queue is exhausted, in which case we throw an exception.

public TItem Dequeue()
{
    if (_subqueues.Any())
        return DequeueFromHighPriorityQueue();
    else
        throw new InvalidOperationException("The queue is empty");
}

The private DequeueFromHighPriorityQueue method extracts the next item in the highest priority queue. If this empties the subqueue, it is removed from the dictionary.

private TItem DequeueFromHighPriorityQueue()
{
    KeyValuePair<TPriority, Queue<TItem>> first = _subqueues.First();
    TItem nextItem = first.Value.Dequeue();
    if (!first.Value.Any())
    {
        _subqueues.Remove(first.Key);
    }
    return nextItem;
}

Peek Method

The last method to add is Peek. This returns the same result as Dequeue but does not remove the returned item from the queue. It allows us to see what the next result will be without affecting the queue's contents. This method is provided by the underlying Queue class so we can simply call the highest priority subqueue's Peek method and return the result.

public TItem Peek()
{
    if (HasItems)
        return _subqueues.First().Value.Peek();
    else
        throw new InvalidOperationException("The queue is empty");
}

Testing the PriorityQueue

Let's test the PriorityQueue class by adding several items of varying priorities then dequeuing all of the items to see the new ordering. The following code does this. In this case the priorities are integers, with a lower number indicating a higher priority. The queue items are strings. In each case the priority has been included in the string to make it easier to interpret the results. Note that the dequeued items are sorted by priority but items of the same priority retain their original ordering.

var queue = new PriorityQueue<int, string>();

queue.Enqueue(1, "A-1");
queue.Enqueue(2, "A-2");
queue.Enqueue(3, "A-3");
queue.Enqueue(1, "B-1");
queue.Enqueue(2, "B-2");
queue.Enqueue(3, "B-3");
queue.Enqueue(1, "C-1");
queue.Enqueue(2, "C-2");
queue.Enqueue(3, "C-3");

while (queue.HasItems)
{
    Console.WriteLine(queue.Dequeue());
}

/* OUTPUT

A-1
B-1
C-1
A-2
B-2
C-2
A-3
B-3
C-3

*/