# Priority Queue

## Overview#

Priority Queue is data structure that behaves like Queue except that the order would change based on priority associated with the element. This feature exists since .NET 6 which is released on November 2021. Compared to other language like Java, the release is too late. Java already had `Priority Queue` since Java 1.5 which was released on September 2004.

Now .NET developers no longer need to write `Priority Queue` from the scratch if they want to solve problem solving questions in `LeetCode` or `HackerRank` that involves `Priority Queue`.

## Priority Queue Basics#

To create Priority Queue, we use class `PriorityQueue<TElement, TPriority>` from `System.Collections.Generic` namespace. `TElement` is the element that will be queued while `TPriority` is the priority associated with the `TElement` that will determine the order of the queue.

If priority is the same, then the element will be ordered in `first in first out` manner just like `Queue`.

Suppose we have following code, where each person is represented as a `String` and associated with a priority represented as `Integer`:

``````PriorityQueue<string, int> priorityQueue = new PriorityQueue<string, int>();
priorityQueue.Enqueue("Tommy", 30);
priorityQueue.Enqueue("Michael", 20);
priorityQueue.Enqueue("Lauren", 40);
priorityQueue.Enqueue("Charles", 40);

while (priorityQueue.TryDequeue(out string element, out int priority))
{
Console.WriteLine(\$"Element: {element}. Priority: {priority}");
}
``````

``````Element: Michael. Priority: 20
Element: Tommy. Priority: 30
Element: Lauren. Priority: 40
Element: Charles. Priority: 40``````

## How to reverse the order of Priority Queue#

The element in previous example is ordered ascendingly by its priority. If we want to order it descendingly, we have to use custom comparer.

There are two ways to create custom comparer:

1. Create a class that implement `IComparer<T>` where `T` is the type of priority

The instance of the class then passed to Priority Queue instance.

``````internal class Program
{
static void Main(string[] args)
{
PriorityQueue<string, int> priorityQueue = new PriorityQueue<string, int>(new PersonComparer());
priorityQueue.Enqueue("Tommy", 30);
priorityQueue.Enqueue("Michael", 20);
priorityQueue.Enqueue("Lauren", 40);
priorityQueue.Enqueue("Charles", 40);

while (priorityQueue.TryDequeue(out string element, out int priority))
{
Console.WriteLine(\$"Element: {element}. Priority: {priority}");
}
}
}

internal class PersonComparer : IComparer<int>
{
public int Compare(int x, int y)
{
return y - x;
}
}
``````

2. Using lambda expression

We pass anonymous method in form of lambda expression to `Create` method of `Comparer` class that accept `Comparison` delegate type. This is because anonymous method can be assigned to delegate type.

``````internal class Program
{
static void Main(string[] args)
{
PriorityQueue<string, int> priorityQueue = new PriorityQueue<string, int>(Comparer<int>.Create((x, y) => y - x));
priorityQueue.Enqueue("Tommy", 30);
priorityQueue.Enqueue("Michael", 20);
priorityQueue.Enqueue("Lauren", 40);
priorityQueue.Enqueue("Charles", 40);

while (priorityQueue.TryDequeue(out string element, out int priority))
{
Console.WriteLine(\$"Element: {element}. Priority: {priority}");
}
}
}
``````

## How to enumerate Priority Queue elements#

To enumerate Priority Queue elements, we can use `UnorderedItems` property. It will enumerate Priority Queue without having to dequeue the element, so the queue won’t be empty or decreasing.

``````PriorityQueue<string, int> priorityQueue = new PriorityQueue<string, int>();
priorityQueue.Enqueue("Tommy", 30);
priorityQueue.Enqueue("Michael", 20);
priorityQueue.Enqueue("Lauren", 40);
priorityQueue.Enqueue("Charles", 40);

foreach (var queueElement in priorityQueue.UnorderedItems)
{
Console.WriteLine(\$"Element: {queueElement.Element}. Priority: {queueElement.Priority}");
}
``````

``````Element: Michael. Priority: 20
Element: Tommy. Priority: 30
Element: Lauren. Priority: 40
Element: Charles. Priority: 40``````

## How to enumerate while dequeuing Priority Queue elements#

There are two ways to enumerate while at the same time dequeuing the elements of Priority Queue:

1. Using `TryDequeue` method

The advantage of using `TryDequeue` is we have access to element’s priority.

``````PriorityQueue<string, int> priorityQueue = new PriorityQueue<string, int>();
priorityQueue.Enqueue("Tommy", 30);
priorityQueue.Enqueue("Michael", 20);
priorityQueue.Enqueue("Lauren", 40);
priorityQueue.Enqueue("Charles", 40);

while (priorityQueue.TryDequeue(out string element, out int priority))
{
Console.WriteLine(\$"Element: {element}. Priority: {priority}");
}
``````

2. Iterating while checking `Count` property, then dequeue the element

The disadvantage of this technique is we don’t have access to element’s priority in case we need it.

``````PriorityQueue<string, int> priorityQueue = new PriorityQueue<string, int>();
priorityQueue.Enqueue("Tommy", 30);
priorityQueue.Enqueue("Michael", 20);
priorityQueue.Enqueue("Lauren", 40);
priorityQueue.Enqueue("Charles", 40);

while (priorityQueue.Count > 0)
{
string element = priorityQueue.Dequeue();
Console.WriteLine(\$"Element: {element}");
}
``````