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

Comments

• Anonymous
  June 14, 2011
  Why not to implement IEnumerable, ICollection?