It’s somewhat surprising in the 20 years .NET (And C#) has been out, there hasn’t been an official implementation of a Priority Queue. It hasn’t stopped people hacking together their own Priority Queues, and indeed, even Microsoft has had several implementations of priority queues buried internally in the framework, but just never exposed for the public. Finally, Microsoft has come to the party and implemented an official Priority queue in .NET 6. Yes, .NET 6.
If you were coming here because you wanted an implementation for .NET Core, .NET 5, or even .NET 4.6.X, then unfortunately you are out of luck. There are implementations floating around the web, but slowly these will go away with the official .NET Priority Queue coming to the framework.
If you are new to .NET 6 and want to know what you need to get started, check out our guide here : https://dotnetcoretutorials.com/2021/03/13/getting-setup-with-net-6-preview/
What Is A Priority Queue?
Before we get started, it’s worth talking about what exactly a Priority Queue is. A Priority Queue is a Queue, where each item holds a “priority” that can be compared against other queue items. When an item is dequeued, the item with the highest priority is popped off the queue, regardless of when it was put on. So if we think of a standard queue as first in, first out (FIFO), and the stack type being last in, first out (LIFO), then a Priority Queue is.. well.. It doesn’t get a nice acronym. It’s more like, whatever in, highest priority out!
Priority can be complex as we will soon see as you can implement custom comparers, but at it’s simplest it could just be a number where the lower the number (e.g. 0 being the highest), the higher the priority.
Priority Queues have many uses, but are most commonly seen when doing work with “graph traversals” as you are able to quickly identify nodes which have the highest/lowest “cost” etc. If that doesn’t make all that much sense to you, it’s not too important. What’s really good to know is that there is a queue out there that can prioritize items for you!
Priority Queue Basics
Consider the very basic example :
using System.Collections.Generic;
PriorityQueue<string, int> queue = new PriorityQueue<string, int>();
queue.Enqueue(“Item A”, 0);
queue.Enqueue(“Item B”, 60);
queue.Enqueue(“Item C”, 2);
queue.Enqueue(“Item D”, 1);
while (queue.TryDequeue(out string item, out int priority))
{
Console.WriteLine($”Popped Item : {item}. Priority Was : {priority}”);
}
The output of this should be relatively easy to predict. If we run it we get :
Popped Item : Item A. Priority Was : 0
Popped Item : Item D. Priority Was : 1
Popped Item : Item C. Priority Was : 2
Popped Item : Item B. Priority Was : 60
The lower the integer, the higher the priority, and we can see our items are always popped based on this priority regardless of the order they were added to the queue. I wish I could extend out this bit of the tutorial but.. It really is that simple!
Using Custom Comparers
The above example is relatively easy to comprehend since the priority is nothing but an integer. But what if we have complex logic on how priority should be derived? We could build this logic ourselves and still use an integer priority, or we could use a custom comparer. Let’s do the latter!
Let’s assume that we are building a banking application. This is a fancy bank in the middle of London city, and therefore there is priority serving of anyone with the title of “Sir” in their name. Even if they show up at the back of the queue, they should get served first (Disgusting I know!).
The first thing we need to do is work out a way to compare titles. For that, this piece of code should do the trick :
class TitleComparer : IComparer<string>
{
public int Compare(string titleA, string titleB)
{
var titleAIsFancy = titleA.Equals(“sir”, StringComparison.InvariantCultureIgnoreCase);
var titleBIsFancy = titleB.Equals(“sir”, StringComparison.InvariantCultureIgnoreCase);
if (titleAIsFancy == titleBIsFancy) //If both are fancy (Or both are not fancy, return 0 as they are equal)
{
return 0;
}
else if (titleAIsFancy) //Otherwise if A is fancy (And therefore B is not), then return -1
{
return -1;
}
else //Otherwise it must be that B is fancy (And A is not), so return 1
{
return 1;
}
}
}
We simply inherit from IComparer, where T is the type we are comparing. In our case it’s just a simple string. Next, we check whether each of the passed in strings are the word “sir”. Then do our ordering based on that. In general, a comparer should return the following :
Return 0 if the two items based in are equal
Return -1 if the first item should be compared “higher” or have higher priority than the second
Return 1 if the second item should be compared “higher” of have higher priority than the first
Now when we create our queue, we can simply pass in our new comparer like so :
PriorityQueue<string, string> bankQueue = new PriorityQueue<string, string>(new TitleComparer());
bankQueue.Enqueue(“John Jones”, “Sir”);
bankQueue.Enqueue(“Jim Smith”, “Mr”);
bankQueue.Enqueue(“Sam Poll”, “Mr”);
bankQueue.Enqueue(“Edward Jones”, “Sir”);
Console.WriteLine(“Clearing Customers Now”);
while (bankQueue.TryDequeue(out string item, out string priority))
{
Console.WriteLine($”Popped Item : {item}. Priority Was : {priority}”);
}
And the output?
Clearing Customers Now
Popped Item : John Jones. Priority Was : Sir
Popped Item : Edward Jones. Priority Was : Sir
Popped Item : Sam Poll. Priority Was : Mr
Popped Item : Jim Smith. Priority Was : Mr
We are now serving all Sirs before everyone else!
When Is Priority Worked Out?
Something I wanted to understand was when is priority worked out? Is it on Enqueue, is it when we Dequeue? Or is it both?
To find out, I edited my custom comparer to do the following :
Console.WriteLine($”Comparing {titleA} and {titleB}”);
Then using the same Enqueue/Dequeue above, I ran the code and this is what I saw :
Comparing Mr and Sir
Comparing Mr and Sir
Comparing Sir and Sir
Clearing Customers Now
Comparing Mr and Mr
Comparing Sir and Mr
Popped Item : John Jones. Priority Was : Sir
Comparing Mr and Mr
Popped Item : Edward Jones. Priority Was : Sir
Popped Item : Sam Poll. Priority Was : Mr
Popped Item : Jim Smith. Priority Was : Mr
So interestingly, we can see that when I am Enqueing, there is certainly comparison’s but only to compare the first node. So as an example, we see 3 compares at the top. That’s because I added 4 items. That tells me there is only a comparison to compare the very top item otherwise it’s likely “heaped”.
Next, notice that when I call Dequeue, there is a little bit of comparison too.. To be honest, I’m not sure why this is. Specifically, there are two comparisons happening when realistically I assumed there would only be one (To compare the current head of the queue to the next).
Next time an item is popped, again we see a single comparison. And then finally, in the last 2 pops, no comparisons at all.
I would love to explain how all of this works but at this point it’s likely going over my head! That being said, it is interesting to understand that Priority is not *just* worked out on Enqueue, and therefore if your IComparer is slow or heavy, it could be running more times than you think.
That being said, the source code is of course open so you are more than welcome to make sense and leave a comment!
How Did We Get Here?
I just want to give a shout out to the fact that Microsoft does so many things with .NET out in the open. You can see back in 2015 the original proposal for PriorityQueue here : https://github.com/dotnet/runtime/issues/14032. Most importantly, it gives the community an insight into how decisions are made and why. Not only that, but benchmarks are given as to different approaches and a few explanations on why certain things didn’t make it into the first cut of the Priority Queue API. It’s really great stuff!
The post PriorityQueue In .NET/C# appeared first on .NET Core Tutorials.
