Priority Queue in C#

Question

I develop a small game using C# and need A* in it. For that, I need a PriorityQueue, which .NET does not have. I wanted to make my own one for practice. Here is it, please comment on performance and usability:

public class PriorityQueue<T> : IEnumerable
{
    List<T> items;
    List<int> priorities;

    public PriorityQueue()
    {
        items = new List<T>();
        priorities = new List<int>();
    }

    public IEnumerator GetEnumerator() { return items.GetEnumerator(); }
    public int Count { get { return items.Count; } }

    /// <returns>Index of new element</returns>
    public int Enqueue(T item, int priority)
    {
        for (int i = 0; i < priorities.Count; i++) //go through all elements...
        {
            if (priorities[i] > priority) //...as long as they have a lower priority.    low priority = low index
            {
                items.Insert(i, item);
                priorities.Insert(i, priority);
                return i;
            }
        }

        items.Add(item);
        priorities.Add(priority);
        return items.Count - 1;
    }

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

    public T Peek()
    {
        return items[0];
    }

    public int PeekPriority()
    {
        return priorities[0];
    }
}

I tested it with...

        PriorityQueue<String> pQ = new PriorityQueue<string>();

        for (int i = 0; i < 100; i++)
        {
            int prio = Provider.Rnd.Next(0, 1000);
            pQ.Enqueue(prio.ToString(), prio);
            if (pQ.Count > 0 && Provider.Rnd.Next(0, 2) == 0) pQ.Dequeue();
        }

        while (pQ.Count > 0)
        {
            Console.WriteLine(pQ.Dequeue());
        }

Answer 1

There are other data structures for priority queues. You might consider implementing the queue as a binary heap instead, which gives you a run-time complexity of O(1) for accessing the "largest" (or "smallest", depending on the comparison) element, and O(log n) for insertion and removal (of the largest).

Answer 2

1. According to my understanding and wikipedia a priority queue serves items with a higher priority first. Your implementation serves items with a lower priority first by inserting them at the front. I guess it depends on your definition of "higher priority" but your comment indicates that you consider lower values as lower priority. So you implementation is a bit counter intuitive.

2. Using an array means you have to copy the entries around when inserting/removing an element at a specific index which means that Enqueue and Dequeue both are O(n) operations.

3. You keep two lists, one for the items and one for the priorities, which are linked by the index in both lists referring to the same element. This requires you to keep both data structures in exact sync which seems a bit of a code smell to me.

Answer 3

You should check some algorithms and implement your priority queue as binary heap. You'll get O(logn) to Dequeue max/min item from queue and Enqueue in O(logn). Here you have sample implementation (note that code is ugly and bad - it's just sample, please don't judge me because I've written it year ago;-) ) http://pastebin.com/FFqj53DW