Priority Queue in C#

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 : IEnumerable
{
    List items;
    List priorities;

    public PriorityQueue()
    {
        items = new List();
        priorities = new List();
    }

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

    /// Index of new element
    public int Enqueue(T item, int priority)
    {
        for (int i = 0; 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 pQ = new PriorityQueue();

        for (int i = 0; i  0 && Provider.Rnd.Next(0, 2) == 0) pQ.Dequeue();
        }

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

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).

StackExchange Code Review Q#38659, answer score: 5