C# Priority Queue

In C#, a priority queue is a data structure that maintains a set of elements with priority. Each element in the queue is assigned a priority value, and elements with higher priority are dequeued first. In this tutorial, we'll discuss how to implement a priority queue in C#.

Syntax

A priority queue can be implemented using a heap data structure. A heap is a binary tree that satisfies the heap property. In a max-heap, each parent node has a value greater than or equal to its children. An example implementation of a max-heap-based priority queue in C# is:

class PriorityQueue<T> where T : IComparable<T>
{
    List<T> data;

    public PriorityQueue()
    {
        this.data = new List<T>();
    }

    public void Enqueue(T item)
    {
        data.Add(item);
        int ci = data.Count - 1;
        while (ci > 0)
        {
            int pi = (ci - 1) / 2;
            if (data[ci].CompareTo(data[pi]) >= 0)
                break;
            T tmp = data[ci]; data[ci] = data[pi]; data[pi] = tmp;
            ci = pi;
        }
    }

    public T Dequeue()
    {
        int li = data.Count - 1;
        T frontItem = data[0];
        data[0] = data[li];
        data.RemoveAt(li);

        --li;
        int pi = 0;
        while (true)
        {
            int ci = pi * 2 + 1;
            if (ci > li) break;
            int rc = ci + 1;
            if (rc <= li && data[rc].CompareTo(data[ci]) < 0)
                ci = rc;
            if (data[pi].CompareTo(data[ci]) <= 0) break;
            T tmp = data[pi]; data[pi] = data[ci]; data[ci] = tmp;
            pi = ci;
        }
        return frontItem;
    }

    public int Count
    {
        get { return data.Count; }
    }
}

Example

Let's say we want to create a priority queue of integers and add some elements to it. Here's how we can implement it:

var pq = new PriorityQueue<int>();
pq.Enqueue(3);
pq.Enqueue(1);
pq.Enqueue(4);
pq.Enqueue(1);
pq.Enqueue(5);

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

Output

When we run the example code above, the output will be:

1
1
3
4
5

This is because we added the elements to the priority queue in the order 3, 1, 4, 1, 5. Since the priority queue maintains elements in ascending order, the elements are dequeued in the order 1, 1, 3, 4, 5.

Explanation

In the example above, we created a priority queue of integers using the PriorityQueue class. We added some elements to it and then dequeued them using the Dequeue method. Since the priority queue maintains elements in ascending order, the elements are dequeued in order of increasing value.

Use

Priority queues are useful when you need to maintain a set of elements with priority, and you want to efficiently retrieve the element with the highest priority. They are commonly used in algorithmic problems, such as Dijkstra's algorithm for finding the shortest path in a graph.

Important Points

• Priority queues can be implemented using a variety of data structures, but a heap-based implementation is one of the most efficient.
• A priority queue can be implemented using a binary max-heap for maximum priority elements or a binary min-heap for minimum priority elements.
• The complexity of enqueueing an item into a priority queue based on a binary heap takes O(log n) time, and dequeuing an item from a heap takes O(log n) time.

Summary

In this tutorial, we discussed how to implement a priority queue in C# using a binary max-heap. We covered the syntax, example, output, explanation, use, and important points of priority queues in C#. With this knowledge, you can now create priority queues in your C# code to maintain elements with priority and retrieve the highest priority element efficiently.