Priority Queue

Tagged: C#, Priority Queue

Overview#

Priority Queue is data structure that behaves like Queue except that the order would change based on priority associated with the element. This feature exists since .NET 6 which is released on November 2021. Compared to other language like Java, the release is too late. Java already had Priority Queue since Java 1.5 which was released on September 2004.

Now .NET developers no longer need to write Priority Queue from the scratch if they want to solve problem solving questions in LeetCode or HackerRank that involves Priority Queue.

Priority Queue Basics#

To create Priority Queue, we use class PriorityQueue<TElement, TPriority> from System.Collections.Generic namespace. TElement is the element that will be queued while TPriority is the priority associated with the TElement that will determine the order of the queue.

If priority is the same, then the element will be ordered in first in first out manner just like Queue.

Suppose we have following code, where each person is represented as a String and associated with a priority represented as Integer:

• C#

PriorityQueue<string, int> priorityQueue = new PriorityQueue<string, int>();
priorityQueue.Enqueue("Tommy", 30);
priorityQueue.Enqueue("Michael", 20);
priorityQueue.Enqueue("Lauren", 40);
priorityQueue.Enqueue("Charles", 40);

while (priorityQueue.TryDequeue(out string element, out int priority))
{
    Console.WriteLine($"Element: {element}. Priority: {priority}");
}

• Output

Element: Michael. Priority: 20
Element: Tommy. Priority: 30
Element: Lauren. Priority: 40
Element: Charles. Priority: 40

How to reverse the order of Priority Queue#

The element in previous example is ordered ascendingly by its priority. If we want to order it descendingly, we have to use custom comparer.

There are two ways to create custom comparer:

1. Create a class that implement IComparer<T> where T is the type of priority
   
   The instance of the class then passed to Priority Queue instance.

   • C#

   internal class Program
   {
       static void Main(string[] args)
       {
           PriorityQueue<string, int> priorityQueue = new PriorityQueue<string, int>(new PersonComparer());
           priorityQueue.Enqueue("Tommy", 30);
           priorityQueue.Enqueue("Michael", 20);
           priorityQueue.Enqueue("Lauren", 40);
           priorityQueue.Enqueue("Charles", 40);
   
           while (priorityQueue.TryDequeue(out string element, out int priority))
           {
               Console.WriteLine($"Element: {element}. Priority: {priority}");
           }
       }
   }
   
   internal class PersonComparer : IComparer<int>
   {
       public int Compare(int x, int y)
       {
           return y - x;
       }
   }
   

2. Using lambda expression
   
   We pass anonymous method in form of lambda expression to Create method of Comparer class that accept Comparison delegate type. This is because anonymous method can be assigned to delegate type.

   • C#

   internal class Program
   {
       static void Main(string[] args)
       {
           PriorityQueue<string, int> priorityQueue = new PriorityQueue<string, int>(Comparer<int>.Create((x, y) => y - x));
           priorityQueue.Enqueue("Tommy", 30);
           priorityQueue.Enqueue("Michael", 20);
           priorityQueue.Enqueue("Lauren", 40);
           priorityQueue.Enqueue("Charles", 40);
   
           while (priorityQueue.TryDequeue(out string element, out int priority))
           {
               Console.WriteLine($"Element: {element}. Priority: {priority}");
           }
       }
   }
   

How to enumerate Priority Queue elements#

To enumerate Priority Queue elements, we can use UnorderedItems property. It will enumerate Priority Queue without having to dequeue the element, so the queue won’t be empty or decreasing.

• C#

PriorityQueue<string, int> priorityQueue = new PriorityQueue<string, int>();
priorityQueue.Enqueue("Tommy", 30);
priorityQueue.Enqueue("Michael", 20);
priorityQueue.Enqueue("Lauren", 40);
priorityQueue.Enqueue("Charles", 40);

foreach (var queueElement in priorityQueue.UnorderedItems)
{
    Console.WriteLine($"Element: {queueElement.Element}. Priority: {queueElement.Priority}");
}

• Output

Element: Michael. Priority: 20
Element: Tommy. Priority: 30
Element: Lauren. Priority: 40
Element: Charles. Priority: 40

How to enumerate while dequeuing Priority Queue elements#

There are two ways to enumerate while at the same time dequeuing the elements of Priority Queue:

1. Using TryDequeue method
   
   The advantage of using TryDequeue is we have access to element’s priority.

   • C#

   PriorityQueue<string, int> priorityQueue = new PriorityQueue<string, int>();
   priorityQueue.Enqueue("Tommy", 30);
   priorityQueue.Enqueue("Michael", 20);
   priorityQueue.Enqueue("Lauren", 40);
   priorityQueue.Enqueue("Charles", 40);
   
   while (priorityQueue.TryDequeue(out string element, out int priority))
   {
       Console.WriteLine($"Element: {element}. Priority: {priority}");
   }
   

2. Iterating while checking Count property, then dequeue the element
   
   The disadvantage of this technique is we don’t have access to element’s priority in case we need it.

   • C#

   PriorityQueue<string, int> priorityQueue = new PriorityQueue<string, int>();
   priorityQueue.Enqueue("Tommy", 30);
   priorityQueue.Enqueue("Michael", 20);
   priorityQueue.Enqueue("Lauren", 40);
   priorityQueue.Enqueue("Charles", 40);
   
   while (priorityQueue.Count > 0)
   {
       string element = priorityQueue.Dequeue();
       Console.WriteLine($"Element: {element}");
   }