Post
Ask Question

PriorityQueue In .NET 6

Intro

I am honestly surprised that after seeing for several years the different implementations of PriorityQueue included internally in Microsoft Frameworks, now they have been exposed publicly, and this thanks to the arrival of .NET 6. In this article, we are going to know the possibilities of PriorityQueue.

Definition

Represents a collection of items that have a value and a priority. On dequeue, the item with the lowest priority value is removed.

Queue

To explain the novelties introduced we are going to create a small class that allows us to work with people.

public class Person
{
    public string Name { get; set; }
    public int Age { get; set; }
}

Let's start by working with Queue. This is a generic data structure in which elements are retrieved in the order they are added.

var persons = new Queue();

persons.Enqueue(new Person() { Name = "Jesus" });
persons.Enqueue(new Person() { Name = "Diego" });
persons.Enqueue(new Person() { Name = "Pablo" });
persons.Enqueue(new Person() { Name = "Angel" });
persons.Enqueue(new Person() { Name = "Hector" });

We are going to use the TryDequeue method which removes the element at the beginning and copies it to the output parameter.

while (persons.TryDequeue(out var person))
{
    Console.WriteLine($"{person.Name}");
}

The output will be something like:

  • Jesus
  • Diego
  • Pablo
  • Angel
  • Hector

Just what we expected and already knew, ordered elements obtaining the first one from the beginning of the collection at all times.

Now imagine that you want to use another criteria to prioritize the order in which elements appear, regardless of the order in which they are queued.

Let's say that in our example, each person has an age and we want to sort using that criteria.

PriorityQueue

We can use the new PriorityQueue class for that purpose, use another criteria to prioritize.

We add several people to a PriorityQueue:

var prioritizedAgents = new PriorityQueue();

prioritizedAgents.Enqueue(new Person() { Name = "Jesus" }, 44);
prioritizedAgents.Enqueue(new Person() { Name = "Diego" }, 32);
prioritizedAgents.Enqueue(new Person() { Name = "Pablo" }, 50); 
prioritizedAgents.Enqueue(new Person() { Name = "Angel" }, 34);
prioritizedAgents.Enqueue(new Person() { Name = "Hector" }, 27);

As we can see in the previous example, the type to be added to the queue and a second type, which will be used for prioritization, are specified.

In our case we have a queue of people and the priority is the age where int is used.

while (prioritizedAgents.TryDequeue(out var person, out var age))
{
    Console.WriteLine($"{person.Name}, age {age}");
}

What's the score?

  • Hector, age 27
  • Diego, age 32
  • Angel, age 34
  • Jesus, age 44
  • Pablo, age 50

People were sorted by age. Therefore, you have to consider the order relative to how they were added to the queue. When prioritizing, a lower value gives a higher priority.

Of course, the type used to define the priority does not have to be a number; can be anything that implements IComparer.

This is an excellent novelty for problems in which the data structures are processed according to the order and also another parameter that gives priority.

More information: .NET Documentation: PriorityQueue


Similar Articles