Priority Queue in C#

Sometimes we may want more than a queue. A queue which has sorting capability.
You may find some familiar built-in classes in .Net framework, like SortedList, but when you only need to take the item with lowest (or highest; depends on the needs and design) priority, SortedList will be a little bit slow, because you will need to sort it after adding new items to the list, everytime.

In addition, if SortedList has more than one items whose Priorities, or keys, are the same, it will throw an exception. So it requires keys to be unique. But in real life examples, you may have some tasks with same priorities, and you may add 'em to your tasklist.


To make it easier to explain; this image represents the behavior the queue we need;

As you can see, dequeue just returns Head of the list, it was a easy function to write just like Count function which returns list size.

Here is classes that I''ve created:

PriorityQueue is the main class, and has a linked list called as Items, which is has linked list nodes that consist QueueItem class.

QueueItem class consists key, which assures priority manners, and obj which is any object that you wanna add into the Queue.




In PriorityQueue class, more important functions are Dequeue and Enqueue for sure. Dequeue is simple and handled by these lines of codes:
        public T Dequeue()
        {
            if (Items.Count == 0)
                return default(T);
            else
            {
                T obj = Items.First.Value.GetObj();
                Items.RemoveFirst();
                return obj;
            }
        }

This codes only returns the head of the linked list if it is not empty. Returns default value that represent null if it is empty.

Other function; Enqueue, adds new object with it's key to the list. Here is the code:

        public void Enqueue(int key, T obj)
        {
            LinkedListNode<QueueItem<T>> node = new LinkedListNode<QueueItem<T>>(new QueueItem<T>(key, obj));
            if (Items.Count == 0)
            {
                Items.AddFirst(node);
            }
            else
            {
                LinkedListNode<QueueItem<T>> current = Items.First;
                while(current != null)
                {
                    if (node.Value.GetKey() <= current.Value.GetKey())
                    {
                        Items.AddBefore(current, node);
                        break;
                    }
                    current = current.Next;
                }
                if (current == null)
                    Items.AddLast(node);
            }
        }

///UPDATE

In the old version, it was not possible to prevent repetitions in the list. With some changes it is possible to create a flag that allows or prevents repetitions in the list.

First we add AllowRepeat boolean attribute to the class;
        private bool AllowRepeat;


And we change the constructor for the class;


        public PriorityQueue(bool RepeatMode)
        {
            Items = new LinkedList<QueueItem<T>>;
            AllowRepeat = RepeatMode;
        }


Only time we need to check for repetitions is when we Enqueue data. So we look at Enqueue function and we add this;


            if (!AllowRepeat)
            {
                if (IsRepetitionExist(key, obj))
                {
                    return;
                }
            }


If AllowRepeat flag is called, it checks  IsRepetitionExist function with sending key and obj to it, and checks if the key already exist in the list. It's a virtual function, we might need to change creteria of duplication in the future.


        public virtual bool IsRepetitionExist(int Key, T obj)
        {
            if (Items.Count == 0)
                return false;
            LinkedListNode<QueueItem <T>> current = Items.First;
           
            int Repetition = 0;
            while (current != null || (current != null && current.Value.GetKey() > Key))
            {
                if (current.Value.GetKey() == Key)
                    Repetition++;
                current = current.Next;
            }
            if (Repetition < 2)
                return false;
            else
                return true;
        }


//END OF UPDATE

First it checks if the list empty; if it is, it is also easy to add to the list by Items.AddFirst(node); command.

If it is not, it checks for every node in the list and it tries to find a node which has higher key (or priority) value than it has. If it finds one, linked list adds new node as previous one of older one, which easily sorts without using other functions.

You can add any objects to the Queue, but Key value must be integer.


Here are the files, ready to use. Only thing you need is to take instance of PriorityQueue class, as easy as;
PriorityQueue<Node> Frontier = new PriorityQueue<Node>();

PriorityQueue.cs
QueueItem.cs

Bon Appetit! :)