C# Priority Queue

Question

I'm looking for a priority queue with an interface like this:

class PriorityQueue<T>
{
    public void Enqueue(T item, int priority)
    {
    }

    public T Dequeue()
    {
    }
}

All the implementations I've seen assume that item is an IComparable but I don't like this approach; I want to specify the priority when I'm pushing it onto the queue.

If a ready-made implementation doesn't exist, what's the best way to go about doing this myself? What underlying data structure should I use? Some sort of self-balancing tree, or what? A standard C#.net structure would be nice.

Solution 1

If you have an existing priority queue implementation based on IComparable, you can easily use that to build the structure you need:

public class CustomPriorityQueue<T>  // where T need NOT be IComparable
{
  private class PriorityQueueItem : IComparable<PriorityQueueItem>
  {
    private readonly T _item;
    private readonly int _priority:

    // obvious constructor, CompareTo implementation and Item accessor
  }

  // the existing PQ implementation where the item *does* need to be IComparable
  private readonly PriorityQueue<PriorityQueueItem> _inner = new PriorityQueue<PriorityQueueItem>();

  public void Enqueue(T item, int priority)
  {
    _inner.Enqueue(new PriorityQueueItem(item, priority));
  }

  public T Dequeue()
  {
    return _inner.Dequeue().Item;
  }
}

Solution 2

You can add safety checks and what not, but here is a very simple implementation using SortedList:

class PriorityQueue<T> {
    SortedList<Pair<int>, T> _list;
    int count;

    public PriorityQueue() {
        _list = new SortedList<Pair<int>, T>(new PairComparer<int>());
    }

    public void Enqueue(T item, int priority) {
        _list.Add(new Pair<int>(priority, count), item);
        count++;
    }

    public T Dequeue() {
        T item = _list[_list.Keys[0]];
        _list.RemoveAt(0);
        return item;
    }
}

I'm assuming that smaller values of priority correspond to higher priority items (this is easy to modify).

If multiple threads will be accessing the queue you will need to add a locking mechanism too. This is easy, but let me know if you need guidance here.

SortedList is implemented internally as a binary tree.

The above implementation needs the following helper classes. This address Lasse V. Karlsen's comment that items with the same priority can not be added using the naive implementation using a SortedList.

class Pair<T> {
    public T First { get; private set; }
    public T Second { get; private set; }

    public Pair(T first, T second) {
        First = first;
        Second = second;
    }

    public override int GetHashCode() {
        return First.GetHashCode() ^ Second.GetHashCode();
    }

    public override bool Equals(object other) {
        Pair<T> pair = other as Pair<T>;
        if (pair == null) {
            return false;
        }
        return (this.First.Equals(pair.First) && this.Second.Equals(pair.Second));
    }
}

class PairComparer<T> : IComparer<Pair<T>> where T : IComparable {
    public int Compare(Pair<T> x, Pair<T> y) {
        if (x.First.CompareTo(y.First) < 0) {
            return -1;
        }
        else if (x.First.CompareTo(y.First) > 0) {
            return 1;
        }
        else {
            return x.Second.CompareTo(y.Second);
        }
    }
}

Solution 3

You could write a wrapper around one of the existing implementations that modifies the interface to your preference:

using System;

class PriorityQueueThatYouDontLike<T> where T: IComparable<T>
{
    public void Enqueue(T item) { throw new NotImplementedException(); }
    public T Dequeue() { throw new NotImplementedException(); }
}

class PriorityQueue<T>
{
    class ItemWithPriority : IComparable<ItemWithPriority>
    {
        public ItemWithPriority(T t, int priority)
        {
            Item = t;
            Priority = priority;
        }

        public T Item {get; private set;}
        public int Priority {get; private set;}

        public int CompareTo(ItemWithPriority other)
        {
            return Priority.CompareTo(other.Priority);
        }
    }

    PriorityQueueThatYouDontLike<ItemWithPriority> q = new PriorityQueueThatYouDontLike<ItemWithPriority>();

    public void Enqueue(T item, int priority)
    {
        q.Enqueue(new ItemWithPriority(item, priority));
    }

    public T Dequeue()
    {
        return q.Dequeue().Item;
    }
}

This is the same as itowlson's suggestion. I just took longer to write mine because I filled out more of the methods. :-s

Solution 4

Here's a very simple lightweight implementation that has O(log(n)) performance for both push and pop. It uses a heap data structure built on top of a List<T>.

/// <summary>Implements a priority queue of T, where T has an ordering.</summary>
/// Elements may be added to the queue in any order, but when we pull
/// elements out of the queue, they will be returned in 'ascending' order.
/// Adding new elements into the queue may be done at any time, so this is
/// useful to implement a dynamically growing and shrinking queue. Both adding
/// an element and removing the first element are log(N) operations. 
/// 
/// The queue is implemented using a priority-heap data structure. For more 
/// details on this elegant and simple data structure see "Programming Pearls"
/// in our library. The tree is implemented atop a list, where 2N and 2N+1 are
/// the child nodes of node N. The tree is balanced and left-aligned so there
/// are no 'holes' in this list. 
/// <typeparam name="T">Type T, should implement IComparable[T];</typeparam>
public class PriorityQueue<T> where T : IComparable<T> {
   /// <summary>Clear all the elements from the priority queue</summary>
   public void Clear () {
      mA.Clear ();
   }

   /// <summary>Add an element to the priority queue - O(log(n)) time operation.</summary>
   /// <param name="item">The item to be added to the queue</param>
   public void Add (T item) {
      // We add the item to the end of the list (at the bottom of the
      // tree). Then, the heap-property could be violated between this element
      // and it's parent. If this is the case, we swap this element with the 
      // parent (a safe operation to do since the element is known to be less
      // than it's parent). Now the element move one level up the tree. We repeat
      // this test with the element and it's new parent. The element, if lesser
      // than everybody else in the tree will eventually bubble all the way up
      // to the root of the tree (or the head of the list). It is easy to see 
      // this will take log(N) time, since we are working with a balanced binary
      // tree.
      int n = mA.Count; mA.Add (item);
      while (n != 0) {
         int p = n / 2;    // This is the 'parent' of this item
         if (mA[n].CompareTo (mA[p]) >= 0) break;  // Item >= parent
         T tmp = mA[n]; mA[n] = mA[p]; mA[p] = tmp; // Swap item and parent
         n = p;            // And continue
      }
   }

   /// <summary>Returns the number of elements in the queue.</summary>
   public int Count {
      get { return mA.Count; }
   }

   /// <summary>Returns true if the queue is empty.</summary>
   /// Trying to call Peek() or Next() on an empty queue will throw an exception.
   /// Check using Empty first before calling these methods.
   public bool Empty {
      get { return mA.Count == 0; }
   }

   /// <summary>Allows you to look at the first element waiting in the queue, without removing it.</summary>
   /// This element will be the one that will be returned if you subsequently call Next().
   public T Peek () {
      return mA[0];
   }

   /// <summary>Removes and returns the first element from the queue (least element)</summary>
   /// <returns>The first element in the queue, in ascending order.</returns>
   public T Next () {
      // The element to return is of course the first element in the array, 
      // or the root of the tree. However, this will leave a 'hole' there. We
      // fill up this hole with the last element from the array. This will 
      // break the heap property. So we bubble the element downwards by swapping
      // it with it's lower child until it reaches it's correct level. The lower
      // child (one of the orignal elements with index 1 or 2) will now be at the
      // head of the queue (root of the tree).
      T val = mA[0];
      int nMax = mA.Count - 1;
      mA[0] = mA[nMax]; mA.RemoveAt (nMax);  // Move the last element to the top

      int p = 0;
      while (true) {
         // c is the child we want to swap with. If there
         // is no child at all, then the heap is balanced
         int c = p * 2; if (c >= nMax) break;

         // If the second child is smaller than the first, that's the one
         // we want to swap with this parent.
         if (c + 1 < nMax && mA[c + 1].CompareTo (mA[c]) < 0) c++;
         // If the parent is already smaller than this smaller child, then
         // we are done
         if (mA[p].CompareTo (mA[c]) <= 0) break;

         // Othewise, swap parent and child, and follow down the parent
         T tmp = mA[p]; mA[p] = mA[c]; mA[c] = tmp;
         p = c;
      }
      return val;
   }

   /// <summary>The List we use for implementation.</summary>
   List<T> mA = new List<T> ();
}

Solution 5

That is the exact interface used by my highly optimized C# priority-queue.

It was developed specifically for pathfinding applications (A*, etc.), but should work perfectly for any other application as well.

public class User
{
    public string Name { get; private set; }
    public User(string name)
    {
        Name = name;
    }
}

...

var priorityQueue = new SimplePriorityQueue<User>();
priorityQueue.Enqueue(new User("Jason"), 1);
priorityQueue.Enqueue(new User("Joseph"), 10);

//Because it's a min-priority queue, the following line will return "Jason"
User user = priorityQueue.Dequeue();

View more solutions

Comments

[mpen]

@Jason: Doesn't that defeat the purpose of a priority queue? It's a queue because the first one in, is the first one out. That's how it's decided. Otherwise it's just a sorted list.

[Yuliy]

This has horrible performance for pop, as you then have to find the first non-empty queue.

[Lasse V. Karlsen]

Problem with SortedList is that it doesn't allow duplicate priorities, so it forces you to ensure unique priorities.

[mpen]

Makes more sense to me that higher numbers correspond to a higher priority.

[Lasse V. Karlsen]

Easily fixed, just negate the priority values, if SortedList is good enough.

[jason]

@Mark: Like I said, that is easily addressed. Using lower number corresponding to higher priorities just makes the implementation simpler so that the ideas are more lucid.

[mpen]

Still trying to find a nice implementation of PriorityQueueThatYouDontLike. Even the ones that uses IComparables don't look very nice.

[Lasse V. Karlsen]

I have a generic heap here: vkarlsen.serveftp.com:81/websvn/…, username and password both 'guest' (without the quotes). The heap still falls prey to the "problem" you mention of requiring IComparable, but you can use the ItemWithPriority class that Mark has posted.

[jason]

He said that he did not want T to have to be IComparable.

[Tarydon]

He wrote "even the ones that uses IComparable don't look very nice" and I was responding to that. The key point is that a priority queue does not require a fully sorted list; all we need to know is which is the first element in the list at any time. The Heap data structure I am using is not fully sorted, but maintains just enough sorting to efficiently implement log(n) insert and remove. Obviously, this is much lighter than a full-blown binary tree will be, and will have same performance overall.

[Tarydon]

To clarify: This PriorityQueue<T> uses no more space than a plain List<T> and has log(n) insert and remove performance.

[mpen]

Tarydon's right, I could use this with the other suggestions about just "generating" an IComparable instead. However, a good PriorityQueue should have O(1) removal, not O(log(n)).

[mpen]

@Yuliy: I thought this too at first, but if we pop off the queues as they become empty, it's not really an issue is it?

[Tarydon]

O(1) removal would mean you maintain a sorted list at all times. That would lead to a n*log(n) time for inserting in the naive case (to re-sort). If you were to use a simple linear list and do a binary search and then insert in, that would still take O(n) time to insert (to shift the elements to make room). And, any tree-based algorithm (like the SortedList) will be O(log(n)) for both insertion and removal (since it will take O(log(n)) to re-balance the tree). So, I am not sure we can actually achieve O(1) removal with O(log(n)) insertion.

[No Refunds No Returns]

You're going to pay somewhere to manage priority. If you have a linked list, you're going to have to walk it on insert to find the "end" of the current priority. Managing priority is not free.

[Yuliy]

I guess you could have a balanced binary search tree of queues, giving you log n performance for the standard operations, but at that point, you might as well just implement a proper heap.

[corlettk]

The only near-O(1) retrieval I've ever seen was a "closest soundex search" using a funky hash-of-the-priority algorithm... the downside was a few of the returned buckets were huge... requiring a human to answer a "Did you mean" question with too many (IMHO) items in the list... but it was damn fast to fetch the list.

[noio]

Looks neat. Unity—for some reason—doesn't provide ElementAt(). So I used Values[0] there.