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.

Answer 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;
  }
}

Answer 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);
        }
    }
}