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! :)

Arama Algoritmalari

Arama Algoritmalari belli bir veri koleksiyonundaki, (Tree) veriler icerisinde, aranilan veriyi bulmamizi saglayan, ve bunu bir yontem kullanarak yapan algoritmalara verilen addir. Arama algoritmasi, ana node'dan aranilan node'a ulasabilecegimiz bir cozum yolu geri dondurebilecegi gibi, cozumun adim-adim yazilmasini gerektirmeyen durumlarda, cozumun kendisini kullaniciya dondurebilir.



Yukarida gordugumuz bir Tree. 103 Tree'nin baslangic noktasi. 103 Node'unu Root Node olarak adlandiriyoruz, kendisi kok cunku. 103 Node'undan 102 ve 104 e giden cubuklar, 103 node'unun 102 ve 104 node'unun parent'i oldugunu gosteriyor. Ayni sekilde 102 ve 104, 103 un child'i.



Ayni sekilde 102, 101 in parenti iken, 105, 104'un childi.

Ornek Tree'miz 3 Level bir Tree. Level 0 da 103 yer alirken, Level 1 de 102 ve 104, level 2 de 101 ve 105 yer almakta.

Arama algoritmasi, yukaridaki gibi bir tree icerisinde, 103 konumunda olan agentimizin, 101 durumuna nasil gelebilecegini bir cozum serisi ile bize geri dondurebilir.

Ornegin, 103 durumundan, 101 e erismek istiyoruz. Izleyecegimiz en efentif yol:

103->102

102->101 'dir.

Cozum 2 aksiyon icermekle beraber, en basit cozumdur. Bunun disinda farkli bir cozum olan:

103->104

104->105

105->104

104->103

103-> 102

102->101, toplam 6 farkli aksiyon icermekte. Kesinlikle en efektif cozum degil.

Sonuc olarak, 103 den 101 e ulasmak icin icin su anlik elimizden 2 farkli yontem var. Her 2 yontem ayri bir arama algoritmasina ait.

Kisacasi, cozume ulasirken izledigimiz her farkli yontem, farkli bir arama algoritmasi. Arama algoritmasi, Current Node'dan, (yukaridaki resimde 103 oldugunu farzediyorum), 102 node'una veya onun yerine 104 node'una dallanmamiza karar veren, ve o node'dan sonra bir sonraki node'a dallanan, bunu sistematik bir yolla yapan, ve aranilan durumu, ya da cozumu, (Solution State) bulana kadar bu sekilde bir dongu icerisinde devam eden algoritmadir.

Treeler uzerinde kullanilan arama algoritmalarini Informed ve Uninformed Search Algorithms olarak ikiye ayirabiliriz.

Informed Search Algorithms, belli bir Heuristic fonksiyonu kullanarak bir zeka piriltisi gostermektedir. Uninformed Search ise herhangi bir zekasal yonteme dayanmadan, suanki Node'dan bir sonraki Node'a gecer.

Bir sonraki yazida uninformed search algoritmasi olan, Breadth-First Searching den bahsedecegim.