PriorityQueues on .NET 7 and C# 11

Read Time:3 Minute, 56 Second

Starting from .NET 6 and C# 10, we finally have built-in support for PriorityQueues 🥳

A PriorityQueue is a collection of items that have a value and a priority; as you can imagine, they act as a queue: the main operations are “add an item to the queue”, called Enqueue, and “remove an item from the queue”, named Dequeue. The main difference from a simple Queue is that on dequeue, the item with lowest priority is removed.

In this article, we’re gonna use a PriorityQueue and wrap it into a custom class to solve one of its design issues (that I hope they’ll be addressed in a future release of dotNET).

Welcoming Priority Queues in .NET

Defining a priority queue is straightforward: you just have to declare it specifying the type of items and the type of priority.

So, if you need a collection of Child items, and you want to use int as a priority type, you can define it as

Now you can add items using the Enqueue method:

And you can retrieve the one on the top of the queue by calling Peek(), if you want to just look at the first item without removing it from the queue:

or Dequeue if you want to retrieve it while removing it from the queue:

This is the essence of a Priority Queue: insert items, give them a priority, then remove them starting from the one with lower priority.

Creating a Wrapper to automatically handle priority in Priority Queues

There’s a problem with this definition: you have to manually specify the priority of each item.

I don’t like it that much: I’d like to automatically assign each item a priority. So we have to wrap it in another class.

Since we’re near Christmas, and this article is part of the C# Advent 2022, let’s use an XMAS-themed example: a Christmas list used by Santa to handle gifts for children.

Let’s assume that the Child class has this shape:

Now we can create a Priority Queue of type <Child, int>:

And wrap it all within a ChristmasList class:

A question for you: what happens when we call the Get method on an empty queue? What should we do instead? Drop a message below! 📩

We need to define a way to assign each child a priority.

Define priority as private behavior

The easiest way is to calculate the priority within the Add method: define a function that accepts a Child and returns an int, and then pass that int value to the Enqueue method.

This approach is useful because you’re encapsulating the behavior in the ChristmasList class, but has the downside that it’s not extensible, and you cannot use different priority algorithms in different places of your application. On the other side, GetPriority is a private operation within the ChristmasList class, so it can be fine for our example.

Pass priority calculation from outside

We can then pass a Func<Child, int> in the ChristmasList constructor, centralizing the priority definition and giving the caller the responsibility to define it:

This implementation presents the opposite problems and solutions we saw in the previous example.

What I’d like to see in the future

This is a personal thought: it’d be great if we had a slightly different definition of PriorityQueue to automate the priority definition.

One idea could be to add in the constructor a parameter that we can use to calculate the priority, just to avoid specifying it explicitly. So, I’d expect that the current definition of the constructor and of the Enqueue method change from this:

to this:

It’s not perfect, and it raises some new problems.

Another way could be to force the item type to implement an interface that exposes a way to retrieve its priority, such as

Again, this approach is not perfect but can be helpful.

Talking about its design, which approach would you suggest, and why?

Further readings

As usual, the best way to learn about something is by reading its official documentation:

🔗 PriorityQueue documentation | Microsoft Learn

This article is part of the 2022 C# Advent (that’s why I chose a Christmas-ish topic for this article),

🔗 C# Advent Calendar 2022

This article first appeared on Code4IT 🐧

Conclusion

PriorityQueue is a good-to-know functionality that is now out-of-the-box in dotNET. Do you like its design? Have you used another library to achieve the same result? In what do they differ?

Let me know in the comments section! 📩

For now, happy coding!

🐧

Source: https://www.code4it.dev/blog/intro-priority-queue

CyberSEO Pro - OpenAI GPT-3 autoblogging and content curation plugin for WordPress