How to Implement Priority Queue in C# Easily

In C#, you can implement a PriorityQueue<TElement, TPriority> using the built-in generic class available from .NET 6 onwards, which stores elements with associated priorities. Alternatively, you can create a custom priority queue using a heap or sorted data structure if targeting earlier versions.

Syntax

The PriorityQueue<TElement, TPriority> class in C# stores elements with their priorities. You add items with Enqueue(element, priority) and remove the highest priority item with Dequeue(). The priority type must support comparison to order the queue.

csharp

PriorityQueue<TElement, TPriority> queue = new PriorityQueue<TElement, TPriority>();
queue.Enqueue(element, priority);
TElement item = queue.Dequeue();

Example

This example shows how to create a priority queue of strings with integer priorities, enqueue items, and dequeue them in priority order.

csharp

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        PriorityQueue<string, int> pq = new PriorityQueue<string, int>();

        pq.Enqueue("Low priority task", 3);
        pq.Enqueue("High priority task", 1);
        pq.Enqueue("Medium priority task", 2);

        while (pq.Count > 0)
        {
            string task = pq.Dequeue();
            Console.WriteLine(task);
        }
    }
}

Output

High priority task
Medium priority task
Low priority task

Common Pitfalls

• Using the wrong priority type that does not support comparison causes runtime errors.
• Assuming Dequeue() returns the lowest priority number; by default, lower priority values are dequeued first.
• Not checking if the queue is empty before dequeuing leads to exceptions.
• For .NET versions before 6, PriorityQueue is unavailable, so a custom implementation is needed.

csharp

/* Wrong: Using Dequeue without checking empty */
// PriorityQueue<string, int> pq = new PriorityQueue<string, int>();
// var item = pq.Dequeue(); // Throws InvalidOperationException if empty

/* Right: Check count before dequeue */
// if (pq.Count > 0) {
//     var item = pq.Dequeue();
// }

Quick Reference

Here is a quick summary of key methods and properties:

Method/Property	Description
Enqueue(TElement element, TPriority priority)	Adds an element with its priority to the queue.
Dequeue()	Removes and returns the element with the highest priority (lowest priority value).
Peek()	Returns the element with the highest priority without removing it.
Count	Gets the number of elements in the queue.

Key Takeaways

Use the built-in PriorityQueue class in .NET 6+ for easy priority queue implementation.

Lower priority values are dequeued first by default, so assign priorities accordingly.

Always check if the queue is empty before calling Dequeue to avoid exceptions.

For older .NET versions, implement a custom priority queue using a heap or sorted list.

Use Enqueue to add items and Dequeue to remove the highest priority item.