A Simple Priority Queue in C#

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace QueueSpace
{
    public class PriorityQueue<TValue> : PriorityQueue<TValue, int> { }

    public class PriorityQueue<TValue, TPriority> where TPriority : IComparable
    {
        private SortedDictionary<TPriority, Queue<TValue>> dict = new SortedDictionary<TPriority, Queue<TValue>>();

        public int Count { get; private set; }
        public bool Empty { get { return Count == 0; } }

        public void Enqueue(TValue val)
        {
            Enqueue(val, default(TPriority));
        }

        public void Enqueue(TValue val, TPriority pri)
        {
            ++Count;
            if (!dict.ContainsKey(pri)) dict[pri] = new Queue<TValue>();
            dict[pri].Enqueue(val);
        }

        public TValue Dequeue()
        {
            --Count;
            var item = dict.Last();
            if (item.Value.Count == 1) dict.Remove(item.Key);
            return item.Value.Dequeue();
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            var pq = new PriorityQueue<int>();

            for (int i = 0; i < 10; ++i)
            {
                pq.Enqueue(i,i/2);
            }
            while (!pq.Empty)
            {
                Console.Write(pq.Dequeue() + " ");
            }

            Console.ReadKey();
        }
    }
}

Output

8 9 6 7 4 5 2 3 0 1

Items with the same priority are dequeued in the same order that they were inserted.

One thought on “A Simple Priority Queue in C#

Leave a Reply

Your email address will not be published. Required fields are marked *