# PriorityQueue

I’m implementing a single-source multiple-target version of Dijkstra's shortest path algorithm that stops when it reaches a requested number of targets.  In order to do this, I’m using a priority queue where target vertices are prioritized by shortest path weight, starting with the source.  The only problem is, the .NET framework doesn’t have a priority queue!  It’s such a simple and common construct that I was rather surprised when I didn’t find one out of the box.  So I implemented a simple one that I’ll share with the rest of you here.

Priority queues can have have many different implementations, but I just used a simple heap along with a dictionary to quickly map from an item to its location in the heap.  This is because a major part of my algorithm requires changing (promoting) the priority of an existing item that’s already in the queue.  In fact, in addition to the standard Enqueue and Dequeue methods, I implemented the indexer as well:

```public TPriority this[T item]
{
get
{
return heap[indexes[item]].Value;
}
set
{
int index;

if (indexes.TryGetValue(item, out index))
{
int order = comparer.Compare(value, heap[index].Value);
if (order != 0)
{
KeyValuePair<T, TPriority> element =                    new KeyValuePair<T, TPriority>(item, value);
if (order < 0)
MoveUp(element, index);
else
MoveDown(element, index);
}
}
else
{
KeyValuePair<T, TPriority> element =               new KeyValuePair<T, TPriority>(item, value);
heap.Add(element);

MoveUp(element, Count);
}
}
}
```

You can add and/or change the priority of any item by using the indexer, and when you do this it starts to feel just like a Dictionary that maps items to priorities.  For this reason, the signature of the PriorityQueue class is PriorityQueue<T, TPriority>.  This may seem a bit backwards if you wanted to think of the priority as the “key” and the item as the “value”, but I wanted to be able to change an item’s priority on the fly, and you can’t change an item’s TKey on the fly in a Dictionary, which is why the order was reversed.

The code for the PriorityQueue class is attached.  Enjoy!

PriorityQueue.cs

Tags

Comments (1)
1. Andrii says:

Why not to implement IEnumerable, ICollection?

Comments are closed.

Skip to main content