.Net 6 is round the corner and in this post, we will continue exploring different features .Net 6/ c# 10 has to offer. For this post, we will focus on the Priority Queue.

Fundamentally Queues are data structures that follow the FIFO (or First In First Out). .Net had an implementation of the Queue for a long time, but when it comes to Priority Queue, developers were left to implement one themselves till now.

So what is a Priority Queue?

Priority Queue is quite similar to the original queue, but with one big difference. Instead of following the FIFO strictly, it gives weightage or priority to the elements in the queue and dequeues elements based on this priority (HIFO ?).

Let us consider the following code.

 var priortyQueue = new PriorityQueue<string,int>(); priortyQueue.Enqueue("C-1",3); priortyQueue.Enqueue("C-2",3); priortyQueue.Enqueue("D", 4); priortyQueue.Enqueue("A",1);  while (priortyQueue.TryDequeue(out var str,out var priority)) {     Console.WriteLine($"Element:{str} with Priority {priority}"); }

This would produce as an output like the following

 Element:A with Priority 1 Element:C-1 with Priority 3 Element:C-2 with Priority 3 Element:D with Priority 4

Despite the fact the Element "A" was enqueued last, the Priority ensures it is dequeued first and hence following the conditions laid out for the Priority Queue. An important point to note here is that there is no guarantee for the elements with the same priority to follow FIFO. This could be verified with the following code.

 var priortyQueue = new PriorityQueue<string,int>(); priortyQueue.Enqueue("A", 1); priortyQueue.Enqueue("C-1",3); priortyQueue.Enqueue("B", 2); priortyQueue.Enqueue("C-2",3); priortyQueue.Enqueue("D", 4);

One cannot guarantee that "C-1" would be printed before "C-2" in this case, even if both hold same priority.

The Priority needn't be integer values nor it needs to use existing default comparers. You can write your own Custom Comparers to be used by the Priority Queue.

For example, consider the following structures defining a Feature Request Priority.

 public record FeatureRequest(bool mustHave,PriorityLevel level);  public enum PriorityLevel {     High,     Medium,     Low, }

You could now use a PriorityQueue as the following

 var customPriorityQueue = new PriorityQueue<string, FeatureRequest>(new CustomComparer()); customPriorityQueue.Enqueue("A", new FeatureRequest(true, PriorityLevel.Medium)); customPriorityQueue.Enqueue("C-1", new FeatureRequest(false, PriorityLevel.High)); customPriorityQueue.Enqueue("B", new FeatureRequest(true, PriorityLevel.High)); customPriorityQueue.Enqueue("C-2", new FeatureRequest(true, PriorityLevel.High)); customPriorityQueue.Enqueue("D", new FeatureRequest(false, PriorityLevel.Low));   while (customPriorityQueue.TryDequeue(out var str, out var priority)) {     Console.WriteLine($"Element:{str} with Priority {priority}"); }

Where the CustomComparer is defined as

 public class CustomComparer : IComparer<FeatureRequest> {     public int Compare(FeatureRequest? x, FeatureRequest? y)     {         return (x, y) switch         {             ({ mustHave: true }, { mustHave: true }) => x.level - y.level,             ({ mustHave: true }, { mustHave: false }) => -1,             ({ mustHave: false }, { mustHave: true }) => 1,             ({ mustHave: false }, { mustHave: false }) => x.level - y.level,         };     } }

The Custom Comparer ensures the "Must Have" Feature Requests are given higher privileges.

Output

 Element:B with Priority FeatureRequest { mustHave = True, level = High } Element:C-2 with Priority FeatureRequest { mustHave = True, level = High } Element:A with Priority FeatureRequest { mustHave = True, level = Medium } Element:C-1 with Priority FeatureRequest { mustHave = False, level = High } Element:D with Priority FeatureRequest { mustHave = False, level = Low }

Hope that provides a quick overview of the PriorityQueue. One of the interesting aspects to consider with Priority Queue is when is the actual priority comparison done? Interestingly it does look to be done during both Enqueue and Dequeue operations. Not sure why, but that would be an interesting topic to look into in one of the future posts.

 This post is ad-supported
​