Priority Queue in C#: How to Use the PriorityQueue Class

Updated on October 28, 2026

A priority queue in C# is the PriorityQueue<TElement, TPriority> class. Every element we enqueue carries a priority, and Dequeue() returns the element with the lowest priority value, not the one that arrived first.

It has plenty of real-world uses, from hospital triage to task schedulers. We have covered the basic Queue in C# already, so it’s a good idea to check it out before continuing with this article.

Let’s dive in.

What Is a Priority Queue in C#?

A priority queue is just a queue, with a twist. In a regular queue, the dequeuing order depends on the enqueuing order: First In, First Out (FIFO). In a priority queue, it depends on the priority of each element, and the element with the highest priority leaves first.

In .NET, that type is PriorityQueue<TElement, TPriority> in the System.Collections.Generic namespace, available since .NET 6. We enqueue each element together with a priority value, and Dequeue() returns the element whose priority value is the lowest. So in C#, a smaller number means a more urgent element.

The priority can be any type. An int works out of the box, as does any type that implements IComparable<T>, and for anything else we pass an IComparer<TPriority> to the constructor.

The queue doesn’t keep its elements sorted: it only knows which one comes next. Elements with equal priorities also aren’t guaranteed to come out in the order they went in, which surprises people who expect queue behaviour.

Let’s imagine a real-life situation. There are several patients in a hospital queue. Some of these patients are more critical to treat, for example, the elderly. We want to serve these patients before others, whenever they come in. That’s a scenario when priority queues are handy.

When we add an element, we also specify a priority to indicate how urgently we need to serve it. The element is compared to other elements in the queue and is positioned accordingly, and the element with the highest priority is served first.

How Do We Use PriorityQueue in C#?

We keep our classes in a console app. The examples that call Assert go into MSTest test methods, in a test project that references the app, and each example that prints to the console replaces the code in the app’s Program.cs. Let’s define our problem by creating the Patient class first:

public class Patient
{
    public string Name { get; set; } = string.Empty;
    public int Age { get; set; }

    public Patient(string name, int age)
    {
        Name = name;
        Age = age;  
    }
}

Priority Queue Capacity

Before we start our solution, let’s explain the underlying data structure used by PriorityQueue. It stores the elements in an array-backed min-heap, where the root node has the highest priority. Microsoft Learn is more precise: the class “Implements an array-backed, quaternary min-heap.” Each node in the heap has up to four children instead of two. Our heap sort article shows how a binary heap works step by step, and the quaternary version follows the same rules. The array heap has an initial capacity and when it gets full and we try to enqueue a new element, a new heap is created with a larger capacity. This is what we mean by the priority queue capacity. We will discuss how we can control the capacity in the next two sections. 

Priority Queue Constructors

Let’s start our solution by creating an instance of PriorityQueue. There is a number of constructors that we can use, let’s start with the parameterless one:

var hospitalQueue = new PriorityQueue<Patient, int>();
Assert.AreEqual(0, hospitalQueue.Capacity);

We create a priority queue with zero capacity and demonstrate this by reading the Capacity property, which .NET 10 added.

Before .NET 10, there was no property to read, so the way to learn the capacity was the EnsureCapacity method. This method takes a number as a parameter and does two things. First, it checks if the queue has enough capacity to contain this number of elements, if not, it expands the capacity of the queue so that it does. Second, the method returns the final capacity. So calling EnsureCapacity(0) returns the current capacity without changing it, and that still works if we target an older version.

Alternatively, we can specify an initial capacity when creating the priority queue:

var hospitalQueue = new PriorityQueue<Patient, int>(5);
Assert.AreEqual(5, hospitalQueue.Capacity);
Assert.AreEqual(0, hospitalQueue.Count);

We notice that the number of elements in the queue is 0, but there’s enough memory allocated for 5 elements. Initializing a capacity can reduce the number of unnecessary memory reallocations, which can be costly.

Finally, we can just pass our collection of patients and their priorities to the constructor:

var patients = new List<(Patient, int)>()
{
    (new("Sarah", 23), 4),
    (new("Joe", 50), 2),
    (new("Elizabeth", 60), 1),
    (new("Natalie", 16), 5),
    (new("Angie", 25), 3)
};
var hospitalQueue = new PriorityQueue<Patient, int>(patients);
Assert.AreEqual(5, hospitalQueue.Capacity);
Assert.AreEqual(5, hospitalQueue.Count);

The priority queue allocates just enough memory for the provided list.

Expanding the Priority Queue Capacity

We have mentioned that when we add a new element to a full priority queue, the back storage is expanded. So how much more memory is allocated? This is controlled by the growth factor. A growth factor is a number that we multiply by the current capacity to increase it. The growth factor in PriorityQueue is two, which means the capacity is doubled on each expansion. This number is a constant and cannot be changed.

Let’s enqueue an element to our current priority queue:

hospitalQueue.Enqueue(new Patient("Roy", 23), 5);
Assert.AreEqual(10, hospitalQueue.Capacity);

It’s worth mentioning that the minimum increment is four. Let’s imagine we have a priority queue with a capacity of one, and we want to add a new element to it. We would expect the capacity to double, to two. But that is an increment of one, and the minimum allowed increment is four. So, the new capacity would instead be five. The current capacity of one plus the minimum increment of four.

We can increase the capacity manually, by calling EnsureCapacity and passing the new number of elements we want to allocate memory for:

Assert.AreEqual(20, hospitalQueue.EnsureCapacity(12));

Here, we tell the priority queue that we want to allocate memory for 12 elements. The current capacity is 10. This method follows the same expansion mechanism, but with one further step. It chooses the maximum of two capacities: the specified capacity that we pass as a parameter, and double the current capacity. So, in the above example, we want to allocate memory for 12 patients, but double the current capacity is 20. So the new capacity is 20. Let’s expand our priority queue even more:

Assert.AreEqual(42, hospitalQueue.EnsureCapacity(42));

We now want to allocate memory for 42 patients, the current capacity is 20, so double that is 40. EnsureCapacity chooses the maximum of 40 and 42.

Releasing the Unnecessary Memory

Now we have so much allocated memory, while only having 6 elements in the priority queue. We can release this unnecessary memory by calling TrimExcess method:

hospitalQueue.TrimExcess();
Assert.AreEqual(6, hospitalQueue.Capacity);

TrimExcess only trims when the queue uses less than 90 percent of its capacity. A queue holding 9 elements in room for 10 keeps its capacity of 10.

Apart from the capacity, we can use the Clear method to remove all the elements:

var patients = new List<(Patient, int)>()
{
    (new("Sarah", 23), 4),
    (new("Joe", 50), 2),
    (new("Elizabeth", 60), 1),
    (new("Natalie", 16), 5),
    (new("Angie", 25), 3)
};
var hospitalQueue = new PriorityQueue<Patient, int>(patients);

hospitalQueue.Clear();

Assert.AreEqual(5, hospitalQueue.Capacity);
Assert.AreEqual(0, hospitalQueue.Count);

We notice that the capacity is still the same, this method only clears the priority queue, without any change to its capacity.

Now that we have covered all the creational aspects of our priority queue, let’s start utilizing it.

Enqueuing and Dequeueing Priority Queue

We know that when we enqueue an element in a priority queue we have to specify a priority value for it. In our example, we set the type of the priority type to int, so when we add an element we have to provide an integer that represents its priority. In the C# implementation, the lowest number has the highest priority (because it’s actually a min-heap, the root node is the minimum). Let’s use the Dequeue method to dequeue an element from our populated priority queue:

var highestPriorityPatient = hospitalQueue.Dequeue();
Assert.AreEqual(60, highestPriorityPatient.Age);
Assert.AreEqual("Elizabeth", highestPriorityPatient.Name);

Having the lowest priority value (being the oldest), Elizabeth has the highest priority and is dequeued first. Now, after Elizabeth has been processed, we expect Joe to be next on the list. Let’s Peek:

var secondHighestPriorityPatient = hospitalQueue.Peek();
Assert.AreEqual(50, secondHighestPriorityPatient.Age);
Assert.AreEqual("Joe", secondHighestPriorityPatient.Name);

We can add new elements to the queue using Enqueue method:

hospitalQueue.Enqueue(new("Roy", 23), 1);
var currentHighestPriorityPatient = hospitalQueue.Peek(); 
Assert.AreEqual(23, currentHighestPriorityPatient.Age); 
Assert.AreEqual("Roy", currentHighestPriorityPatient.Name);

We added a new patient, Roy, with the priority 1, which is currently the lowest priority value in our queue now. Although he is the last in, he is the first out.

Another useful method that we can use to enqueue and dequeue at the same time is EnqueueDequeue. Since .NET 8, it has a twin called DequeueEnqueue, and the order in the name is the order of the work. Let’s start two queues from our five patients and give both methods a new patient, Roy, with priority 0, more urgent than anyone already waiting:

var patientToAdd = new Patient("Roy", 80);

var firstQueue = new PriorityQueue<Patient, int>(patients);
var returnedByEnqueueDequeue = firstQueue.EnqueueDequeue(patientToAdd, 0);
Assert.AreEqual("Roy", returnedByEnqueueDequeue.Name);
Assert.AreEqual("Elizabeth", firstQueue.Peek().Name);

var secondQueue = new PriorityQueue<Patient, int>(patients);
var returnedByDequeueEnqueue = secondQueue.DequeueEnqueue(patientToAdd, 0);
Assert.AreEqual("Elizabeth", returnedByDequeueEnqueue.Name);
Assert.AreEqual("Roy", secondQueue.Peek().Name);

EnqueueDequeue adds Roy first and then dequeues the highest priority element, which is now Roy himself. So he comes straight back, and Elizabeth stays at the front. DequeueEnqueue dequeues Elizabeth first and only then adds Roy, so Roy is the one waiting at the front.

When the new element is not the most urgent one, both methods return Elizabeth. The difference also shows on an empty queue: EnqueueDequeue hands back the element we gave it, while DequeueEnqueue throws an InvalidOperationException, just like Dequeue.

Equal Priorities

We have agreed that the order of processing the elements of the priority queue merely depends on the priority value. But what if the priority values are equal? Do we revert to the queue first-in-first-out basics?

Well, not quite.

In fact, if the priorities are equal among two or more elements, there is no guarantee which element will be processed first. Microsoft Learn says so directly: “the type does not guarantee first-in-first-out semantics for elements of equal priority.” Let’s create a new priority queue to demonstrate:

var hospitalQueue = new PriorityQueue<Patient, int>(5);
hospitalQueue.Enqueue(new("Sarah", 23), 1);
hospitalQueue.Enqueue(new("Joe", 50), 1);
hospitalQueue.Enqueue(new("Elizabeth", 60), 1);
hospitalQueue.Enqueue(new("Natalie", 16), 1);
hospitalQueue.Enqueue(new("Angie", 25), 1);

while (hospitalQueue.Count > 0)
    Console.WriteLine(hospitalQueue.Dequeue().Name);

We gave all the elements the same priority, dequeued them, and wrote them to the console:

Sarah
Angie
Natalie
Elizabeth
Joe

They are not dequeued in the same order they were enqueued. We conclude that, although being a queue, the priority queue has nothing to do with FIFO.

How Do We Implement a Custom Priority Comparer?

In our current implementation, we provided a number for each patient that specifies their priority. We had to make sure we give older patients higher priorities. But what if we can provide our priority queue with some logic that calculates the priority for each patient on the go? We can achieve that by providing the priority queue with an implementation of IComparer:

public class HospitalQueueComparer : IComparer<Patient>
{
    public int Compare(Patient? x, Patient? y)
    {
        ArgumentNullException.ThrowIfNull(x);
        ArgumentNullException.ThrowIfNull(y);

        if (x.Age == y.Age)
            return 0;
        else if (x.Age > y.Age)
            return -1;
        else
            return 1;
    }
}

We create a class that implements IComparer. The interface declares Compare with nullable parameters, so we check both with ThrowIfNull before we touch them. Then the method compares two patients according to their ages. Remember that in our C# implementation, the less the priority value, the higher the priority. So the method returns:

• 0 if both patients are the same age
• -1 (less than) if x is older than y
• 1 (greater than) if x is younger than y 

This is also how we get a max priority queue, where the highest number wins: the class is always a min-heap, so we reverse the comparison, for example with new PriorityQueue<Patient, int>(Comparer<int>.Create((x, y) => y.CompareTo(x))). If IComparer versus IComparable is new to you, our article on custom comparers covers both, along with the Comparison delegate.

Now, let’s provide our priority queue with an instance of this class:

var patients = new List<Patient>()
{
    new("Sarah", 23),
    new("Joe", 50),
    new("Elizabeth", 60),
    new("Natalie", 16),
    new("Angie", 25),
};
var hospitalQueue = new PriorityQueue<Patient, Patient>(new HospitalQueueComparer());
patients.ForEach(p => hospitalQueue.Enqueue(p, p));

We make a slight change to our list, it no longer contains priority numbers. We are using the patient object to calculate their priority. Then, we create a priority queue, passing an instance of HospitalQueueComparer. Finally, we populate our queue.

Let’s run the same tests to see if we get the same results:

var highestPriorityPatient = hospitalQueue.Dequeue();
Assert.AreEqual(60, highestPriorityPatient.Age);
Assert.AreEqual("Elizabeth", highestPriorityPatient.Name);

var secondHighestPriorityPatient = hospitalQueue.Peek();
Assert.AreEqual(50, secondHighestPriorityPatient.Age);
Assert.AreEqual("Joe", secondHighestPriorityPatient.Name);

We see that Elizabeth, the oldest, has the highest priority. Joe who’s fifty is next on the list. Great! Now we can guarantee that older patients get treated first.

When Is Priority Calculated?

Now that we have a custom comparing method, we can know when and how the PriorityQueue sorts the elements, by spotting when the Compare method runs. Let’s make some changes to the Compare method:

public int Compare(Patient? x, Patient? y)
{
    ArgumentNullException.ThrowIfNull(x);
    ArgumentNullException.ThrowIfNull(y);

    Console.WriteLine($"Comparing {x.Name} and {y.Name}");
    Console.WriteLine();

    if (x.Age == y.Age)
        return 0;
    else if (x.Age > y.Age)
        return -1;
    else
        return 1;
}

We enqueue the patients first and print each name as it goes in:

var patients = new List<Patient>()
    {
        new("Sarah", 23),
        new("Joe", 50),
        new("Elizabeth", 60), 
        new("Natalie", 16),
        new("Angie", 25),
    };
var hospitalQueue = new PriorityQueue<Patient, Patient>(new HospitalQueueComparer());
patients.ForEach(p => {
    Console.WriteLine($"Enqueueing {p.Name}"); 
    hospitalQueue.Enqueue(p, p);
});

Now, let’s check out the output and break it down:

Enqueueing Sarah
Enqueueing Joe
Comparing Joe and Sarah

Enqueueing Elizabeth
Comparing Elizabeth and Joe

Enqueueing Natalie
Comparing Natalie and Elizabeth

Enqueueing Angie
Comparing Angie and Elizabeth

First, we enqueue Sarah, which is now the only patient in the queue, no need for comparison. Then we enqueue Joe and compare him with Sarah. Now, Sarah is younger, so Joe becomes the root element. Next, we enqueue Elizabeth, she’s compared with Joe. Elizabeth is older, so she is now the root element.

The last two elements are both compared to Elizabeth, which is the oldest and remains the root element. The heap is quaternary, so the root has room for four children. Joe, Sarah, Natalie and Angie all sit directly under Elizabeth, and each new patient only needs to beat their parent. That’s it, no more comparisons. So, the PriorityQueue instance makes just enough comparisons to specify the root element. It only knows which element to serve on the next Dequeue() call.

Now let’s explore the dequeuing operations:

...
Console.WriteLine("Dequeuing");

while (hospitalQueue.Count > 0)
    Console.WriteLine($"Dequeuing {hospitalQueue.Dequeue().Name}");

Let’s check out the output and break it down as well:

...
Dequeuing
Comparing Joe and Sarah

Comparing Natalie and Joe

Comparing Angie and Joe

Dequeuing Elizabeth
Comparing Angie and Sarah

Comparing Natalie and Angie

Dequeuing Joe
Comparing Natalie and Sarah

Dequeuing Angie
Dequeuing Sarah
Dequeuing Natalie

The first thing we notice is that the comparisons print before “Dequeuing Elizabeth”. That’s because Console.WriteLine only runs once Dequeue() has returned, and all of these comparisons happen inside that one call. Dequeue() takes Elizabeth out of the root, moves the last element in the array, Angie, into the gap, and then looks for the most urgent of the remaining children. Joe beats Sarah and Natalie, and then Joe beats Angie, so Joe becomes the new root. So, PriorityQueue finds the next element it’s going to serve while it dequeues the current one. If we continue, we see that the same pattern repeats.

This means that the elements are not stored in an ordered fashion, instead, the PriorityQueue only calculates the highest priority element on each enqueuing and dequeuing operation. 

How Do We Remove an Element or Change Its Priority?

Since .NET 9, PriorityQueue<TElement, TPriority> has a Remove() method. We pass the element we want gone, and it hands back the removed element and its priority through two out parameters. It returns false when the element isn’t in the queue.

By default, Remove() looks for the element with EqualityComparer<TElement>.Default. For a class like our Patient, that means reference equality, so we pass the same instance we enqueued. An optional fourth parameter takes an IEqualityComparer<TElement> if we’d rather match by name or by ID.

There’s no method that changes a priority in place. To reprioritize a patient, we remove them and enqueue them again with the new priority.

Removal costs more than the other operations. The queue has to search its array for the element, so the time grows with the number of elements, while Enqueue() and Dequeue() only walk one path through the heap.

Let’s say Joe’s condition gets worse while he waits, and we want to see him first:

var patients = new List<(Patient, int)>()
{
    (new("Sarah", 23), 4),
    (new("Joe", 50), 2),
    (new("Elizabeth", 60), 1),
    (new("Natalie", 16), 5),
    (new("Angie", 25), 3)
};
var joe = patients[1].Item1;
var hospitalQueue = new PriorityQueue<Patient, int>(patients);

var removed = hospitalQueue.Remove(joe, out var removedPatient, out var oldPriority);

Assert.IsTrue(removed);
Assert.AreEqual("Joe", removedPatient?.Name);
Assert.AreEqual(2, oldPriority);
Assert.AreEqual(4, hospitalQueue.Count);

hospitalQueue.Enqueue(joe, 0);
Assert.AreEqual("Joe", hospitalQueue.Peek().Name);

We keep a reference to the Patient object we enqueued, because that’s what Remove() compares against. Remove() gives us back Joe and his old priority, 2. We enqueue him again with priority 0, and now he’s the next patient we serve.

On .NET 8 or older there is no Remove(), and the workaround is to build a new queue from every element except the one we want gone.

To find out what’s in the queue without dequeuing anything, we use the UnorderedItems property. As the name says, it enumerates element and priority pairs in the order they sit in the heap’s array, not in priority order. For our five patients, it lists Elizabeth, Joe, Sarah, Natalie and Angie, so Angie with priority 3 comes after Natalie with priority 5.

Is PriorityQueue Thread-Safe?

An instance of PriorityQueue is not thread-safe. Although we have a thread-safe implementation of the regular queue in C#, ConcurrentQueue, we still don’t have that for the priority queue. So, if we’re working in a multithreaded environment, we have to tackle race conditions ourselves when working with PriorityQueue. The simplest way is to put every call behind one lock:

public class SynchronizedHospitalQueue
{
    private readonly PriorityQueue<Patient, int> _queue = new();
    private readonly Lock _lock = new();

    public void Enqueue(Patient patient, int priority)
    {
        lock (_lock)
        {
            _queue.Enqueue(patient, priority);
        }
    }

    public bool TryDequeue(out Patient? patient)
    {
        lock (_lock)
        {
            return _queue.TryDequeue(out patient, out _);
        }
    }
}

Since .NET 9, the System.Threading.Lock type is the dedicated object for a lock statement. Every operation goes through the same lock, so only one thread touches the heap at a time. We use TryDequeue rather than Count followed by Dequeue, because another thread could empty the queue between those two calls. For more on the lock statement itself, see our article on locking in C#.

Conclusion  

In this article, we have learned how to create a priority queue in C#. We have discussed how we enqueue and dequeue elements, their processing order, and the underlying data structure. Also, we have implemented a custom priority comparer with our custom sorting logic, through which we were able to understand the mechanism that the queue uses to achieve its functionality. Finally, we’ve seen how to remove an element or change its priority with Remove(), and how to share a queue between threads safely.

Tested with .NET 10.0.10 (SDK 10.0.302) and MSTest 4.5.1.