Starting with .NET 6 and C# 10, we finally have built-in support for PriorityQueues 🥳
PriorityQueue is a collection of items that have value and priority; As you can imagine, they act as a queue: the main actions are “add item to queue”, which is called turnand “Remove item from queue”, named turn. The main difference from a simple queue is that in the queue, the item with Lowest priority has been removed.
In this article, we will use a PriorityQueue and wrap it in a custom class to solve one of its design issues (which I hope will be addressed in a future dotNET release).
Getting priority queues in .NET
Setting up a priority queue is simple: you just have to declare it specifying the item type and the priority type.
So, if you need a collection of Child items, and you want to use them int As a priority type, you can set it as
PriorityQueue<Child, int> pq = new PriorityQueue<Child, int>();Now you can add items using Enqueue method:
Child child =
int priority = 3;
queue.Enqueue(child, priority);And you can retrieve the one at the top of the queue by calling Peek()If you want to just look at the first item without removing it from the queue:
Child child3 = BuildChild3();
Child child2 = BuildChild2();
Child child1 = BuildChild1();
queue.Enqueue(child3, 3);
queue.Enqueue(child1, 1);
queue.Enqueue(child2, 2);
Child first = queue.Peek();
or Dequeue If you want to retrieve it while removing it from the queue:
Child child3 = BuildChild3();
Child child2 = BuildChild2();
Child child1 = BuildChild1();
queue.Enqueue(child3, 3);
queue.Enqueue(child1, 1);
queue.Enqueue(child2, 2);
Child first = queue.Dequeue();
This is the essence of a priority queue: put items in, prioritize them, then remove them starting with the lowest priority.
Creating a wrapper for automatic priority handling in priority queues
There is a problem with this setup: you have to manually specify the priority of each item.
I don’t like it so much: I want to automatically assign each item a priority. So we need to wrap it in another class.
Since we’re close to Christmas, and this article is part of C# Advent 2022, let’s use a Christmas-themed example: a Christmas list used by Santa to handle children’s gifts.
Let’s assume the Child class has this form:
public class Child
{
public bool HasSiblings { get; set; }
public int Age { get; set; }
public List<Deed> Deeds { get; set; }
}
public abstract class Deed
{
public string What { get; set; }
}
public class GoodDeed : Deed
{ }
public class BadDeed : Deed
{ }Now we can create a priority queue of sorts <Child, int>:
PriorityQueue<Child, int> pq = new PriorityQueue<Child, int>();and wrap it all in a ChristmasList status:
public class ChristmasList
{
private readonly PriorityQueue<Child, int> queue;
public ChristmasList()
{
queue = new PriorityQueue<Child, int>();
}
public void Add(Child child)
{
int priority =
queue.Enqueue(child, priority);
}
public Child Get()
{
return queue.Dequeue();
}
}A question for you: what happens when we call
GetA method on an empty queue? What should we do instead? Send 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 using the Add method: define a function that accepts a Child and returns an intThen pass it on int value to Enqueue method.
public void Add(Child child)
{
int priority = GetPriority(child);
queue.Enqueue(child, priority);
}This approach is useful because you wrap the behavior in ChristmasList class, but it has the disadvantage that it is not extensible, and you cannot use different priority algorithms in different places of your application. On the other hand, GetPriority is a private operation inside ChristmasList in the classroom, so it could be fine for our example.
pass priority calculation from the outside
After that we can pass a Func<Child, int> In the ChristmasList A constructor, centralizes the priority setting and gives the caller the responsibility to set it:
public class ChristmasList
{
private readonly PriorityQueue<Child, int> queue;
private readonly Func<Child, int> _priorityCalculation;
public ChristmasList(Func<Child, int> priorityCalculation)
{
queue = new PriorityQueue<Child, int>();
_priorityCalculation = priorityCalculation;
}
public void Add(Child child)
{
int priority = _priorityCalculation(child);
queue.Enqueue(child, priority);
}
public Child Get()
{
return queue.Dequeue();
}
}This application presents the opposite problems and solutions we saw in the previous example.
What I would like to see in the future
This is a personal thought: it would be great if we had a slightly different definition of PriorityQueue to make the priority setting automatic.
One idea could be to add a parameter in the constructor that we can use to calculate the priority, just to avoid specifying it explicitly. So, I would expect the current definition of the constructor and the Enqueue method to change from here:
PriorityQueue<Child, int> pq = new PriorityQueue<Child, int>();
int priority = _priorityCalculation(child);
queue.Enqueue(child, priority);to this:
PriorityQueue<Child, int> pq = new PriorityQueue<Child, int>(_priorityCalculation);
queue.Enqueue(child);It’s not perfect, and it raises some new issues.
Another way could be to force the item type to implement an interface that exposes a way to retrieve its priority, such as
public interface IHavePriority<T>{
public T GetPriority();
}
public class Child : IHavePriority<int>{}Again, this approach is not perfect but can be helpful.
Talking about its design, Which approach would you suggest and why?
Additional 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 2022 C# Advent (that’s why I chose Christmas theme for this article),
This article first appeared on Code4IT 🐧
Summary
PriorityQueue is a good to know functionality that is now out of the box in dotNET. Do you like its design? Did you use a different library to achieve the same result? How do they differ?
Tell me in the comments section! 📩
For now, happy coding!
🐧
.
