Priority Queue in C# is a very useful data structure that has so many real-world applications. In this article, we are going to cover the main concepts of Priority Queue in C#. We have covered the basic Queue in C#, it is recommended to check it out before continuing with this article.
Let’s dive in.
What Is a Priority Queue in C#?
Priority Queue is just a queue, with a twist. While the dequeuing order in a regular queue depends on the enqueuing precedence – First In First Out (FIFO), in a priority queue it depends on the priority of the element. In other words, the element that has the highest priority is dequeued first.
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:
Basic Priority Queue in C# Example
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. 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 section.
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.EnsureCapacity(0));
We create a priority queue with zero capacity and demonstrate this by calling 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 we can always know the current capacity by calling EnsureCapacity and passing 0 as an argument.
Alternatively, we can specify an initial capacity when creating the priority queue:
var hospitalQueue = new PriorityQueue<Patient, int>(5); Assert.AreEqual(5, hospitalQueue.EnsureCapacity(0)); 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.EnsureCapacity(0));
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.EnsureCapacity(0));
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. Although we would expect the capacity to be double, which is two. But, this is actually 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.EnsureCapacity(0));
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.EnsureCapacity(0));
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(highestPriorityPatient.Age, 60); Assert.AreEqual(highestPriorityPatient.Name, "Elizabeth");
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(secondHighestPriorityPatient.Age, 50); Assert.AreEqual(secondHighestPriorityPatient.Name, "Joe");
We can add new elements to the queue using Enqueue method:
hospitalQueue.Enqueue(new("Roy", 23), 1);
var currentHighestPriorityPatient = hospitalQueue.Peek();
Assert.AreEqual(currentHighestPriorityPatient.Age, 23);
Assert.AreEqual(currentHighestPriorityPatient.Name, "Roy");
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:
var patientToAdd = new Patient("Roy", 59);
var highestPriorityPatient = hospitalQueue.EnqueueDequeue(patientToAdd, patientToAdd);
Assert.AreEqual(highestPriorityPatient.Age, 60);
Assert.AreEqual(highestPriorityPatient.Name, "Elizabeth");
var secondHighestPriorityPatient = hospitalQueue.Peek();
Assert.AreEqual(secondHighestPriorityPatient.Age, 59);
Assert.AreEqual(secondHighestPriorityPatient.Name, "Roy");
In the above code, we dequeue the highest priority patient, Elizabeth, and simultaneously enqueue Roy, who’s now the oldest and the highest priority element.
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 way we can tell which element will be processed first. 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.
Implementing 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)
{
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 create a class that implements IComparer. The Compare 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:
0if both patients are the same age-1(less than) ifxis older thany1(greater than) ifxis younger thany
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(highestPriorityPatient.Age, 60); Assert.AreEqual(highestPriorityPatient.Name, "Elizabeth"); var secondHighestPriorityPatient = hospitalQueue.Peek(); Assert.AreEqual(secondHighestPriorityPatient.Age, 50); Assert.AreEqual(secondHighestPriorityPatient.Name, "Joe");
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)
{
Console.WriteLine($"Comparing {x.Name} and {y.Name}\n\r");
if (x.Age == y.Age)
return 0;
else if(x.Age > y.Age)
return -1;
else
return 1;
}
Let’s explore the enqueueing operations first:
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. 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 before the first dequeue, all the child elements are compared to each other. We also notice that the comparison logic is similar to the first one, it only aims to find the next highest priority element. Here, it’s Joe. So, only now that PriorityQueue knows the next element it’s going to serve, it dequeues Elizabeth. 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.
Thread Safety of Priority Queue in C#
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.
Conclusion
In this article, we have learned how to create a priority queue in C#. We have discussed how we enqueue and dequeued elements, their processing order, and the underlying data structure. Also, we have implemented a custom priority queue with our customer sorting logic, through which we were able to understand the mechanism that the queue uses to achieve its functionality.
