C# PriorityQueue<TElement, TPriority>: How to Use It

A C# priority queue is built right into the base class library: PriorityQueue<TElement, TPriority> under System.Collections.Generic. You enqueue a value with a priority, and TryDequeue always gives you back the element with the lowest priority first, not the one that’s been waiting longest.

var queue = new PriorityQueue<string, int>();
queue.Enqueue("low priority", 2);
queue.Enqueue("high priority", 1);
queue.TryDequeue(out var item, out _); // "high priority"

PriorityQueue shipped in .NET 6 and the API hasn’t changed since, so everything below still applies on current .NET versions. This post will explore what a PriorityQueue is, how we add elements, and how we can dequeue them.

What Is A Queue?

Queues are a fundamental first in, first out data structure in computer science. Queues are ideal for processing datasets that must track an exact order. Elements dequeued are removed from the collection, meaning a queue’s size is in constant flux. Let’s take a look at a straightforward example using .NET’s Queue data structure.

Queue<string> numbers = new Queue<string>();
numbers.Enqueue("one");
numbers.Enqueue("two");
numbers.Enqueue("three");
numbers.Enqueue("four");
numbers.Enqueue("five");

// A queue can be enumerated without disturbing its contents.
while(numbers.TryDequeue(out var number) )
{
    Console.WriteLine(number);
}

Console.WriteLine(numbers.Count);

A call to TryDequeue will remove and return the value at the front of the queue. In the case of this example, we can expect our execution will result in the following output.

one
two
three
four
five
0

Now that we understand how a Queue operates, how is a PriorityQueue different?

What Is A Priority Queue?

Like a queue, a PriorityQueue is still a first in, first out structure. The difference is a user-specified priority determines what element is “first” and not the order in which we add values. In the case of .NET 6, the PriorityQueue type determines the priority of values using an implementation of the IComparer interface. Let’s take a look at a quick sample. We’ll be adding Superheroes to a new PriorityQueue by their Greatness.

A PriorityQueue takes two generic arguments, the first being the value of the item in the queue and the second being the priority type. The constructor can also take an IComparer instance but is not required since most primitive types in .NET already have a default comparer implementation.

using System;
using System.Collections.Generic;
using static Greatness;

PriorityQueue<string, Greatness> superheroes
    = new(new GreatnessComparer());

superheroes.Enqueue("Hawkeye", Meh);
superheroes.Enqueue("Captain America", GOAT);
superheroes.Enqueue("Mantis", Ok);
superheroes.Enqueue("Scarlet Witch", Good);
superheroes.Enqueue("Black Widow", Meh);
superheroes.Enqueue("Spider-Man", Great);
superheroes.Enqueue("Dr. Strange", Good);
superheroes.Enqueue("Thor", Great);
superheroes.Enqueue("Shuri", Great);
superheroes.Enqueue("Black Panther", Great);
superheroes.Enqueue("Iron Man", Ok);
superheroes.Enqueue("Hulk", Good);

Console.WriteLine("Oh No! Hydra is attacking.");
Console.WriteLine("Avengers... Assemble!");

while (superheroes.TryDequeue(out var hero, out var greatness))
{
    Console.WriteLine($"{hero} ({greatness}) has joined the fight...");
}

public class GreatnessComparer: IComparer<Greatness>
{
    // highest to lowest
    public int Compare(Greatness x, Greatness y) => y - x;
}

public enum Greatness
{
    Meh,
    Ok,
    Good,
    Great,
    GOAT
}

In the example, we’ll see our superheroes join the fight by their Greatness from highest to lowest. PriorityQueue will determine our superheroes’ priority using the IComparer implementation of GreatnessComparer. Executing the program, we should see the following output.

Oh No! Hydra is attacking.
Avengers... Assemble!
Captain America (GOAT) has joined the fight...
Spider-Man (Great) has joined the fight...
Thor (Great) has joined the fight...
Shuri (Great) has joined the fight...
Black Panther (Great) has joined the fight...
Hulk (Good) has joined the fight...
Dr. Strange (Good) has joined the fight...
Scarlet Witch (Good) has joined the fight...
Mantis (Ok) has joined the fight...
Iron Man (Ok) has joined the fight...
Hawkeye (Meh) has joined the fight...
Black Widow (Meh) has joined the fight...

Phew! We can see that Earth’s mightiest heroes started the fight, giving Hawkeye and Black Widow a chance to survive.

Conclusion

The PriorityQueue data structure is a welcome addition to the System.Collections.Generic namespace, and I’m excited to see how folks use it in their applications. It differs from a Queue as the definition of first is subject and based on the IComparer implementation, which can determine the order on any set of variables.

I hope you found this post helpful, and please feel free to leave a comment and share this post.