Kael Rowan

Foundations of Elegant Code

PriorityQueue

PriorityQueue

  • Comments 1

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!

Attachment: PriorityQueue.cs
  • Why not to implement IEnumerable, ICollection?

Page 1 of 1 (1 items)
Leave a Comment
  • Please add 7 and 2 and type the answer here:
  • Post