Priority Queues in C#

Priority queues plays an important role in effective task management systems, where tasks are assigned priority levels based on their urgency, importance, or other criteria. By using priority queues, tasks can be organized and processed according to their priority, ensuring that critical tasks are handled promptly while maintaining order and efficiency in task execution.

What is a Priority Queue in C#?

A priority queue is a type of data structure that organizes elements based on their priority levels. Unlike traditional queues, where elements are processed in the order they are added (first-in-first-out), priority queues prioritize elements according to a predefined criterion. Elements with higher priority are processed before those with lower priority. Priority queues are commonly used in scenarios where tasks need to be executed based on their urgency, importance, or other criteria, allowing for efficient task management and resource allocation.

Comparison of Priority Queue with Standard Queue

In contrast to standard queues, which adhere strictly to the FIFO principle, priority queues introduce the concept of prioritization. While both data structures maintain the order of elements, priority queues allow for the retrieval of elements based on their priority levels, rather than their arrival order. This distinction makes priority queues particularly suitable for applications where the importance or urgency of tasks varies, offering a flexible and efficient solution for task management.

Implementing Priority Queues in C#

Using Built-in Data Structures

• Priority Queue with Sorted List

A priority queue can be implemented using a sorted list in C#. The SortedList<TKey, TValue> class provides an efficient way to maintain a collection of key-value pairs sorted by keys. In this implementation, the keys represent the priority levels, and the values represent the elements of the priority queue.

using System;
using System.Collections;

public class PriorityQueueWithSortedList<TPriority, TValue> where TPriority : IComparable
{
    private SortedList<TPriority, TValue> sortedList;

    public PriorityQueueWithSortedList()
    {
        sortedList = new SortedList<TPriority, TValue>();
    }

    public void Enqueue(TPriority priority, TValue value)
    {
        sortedList.Add(priority, value);
    }

    public TValue Dequeue()
    {
        if (sortedList.Count == 0)
        {
            throw new InvalidOperationException("The priority queue is empty.");
        }

        var value = sortedList.Values[0];
        sortedList.RemoveAt(0);
        return value;
    }

    public TValue Peek()
    {
        if (sortedList.Count == 0)
        {
            throw new InvalidOperationException("The priority queue is empty.");
        }

        return sortedList.Values[0];
    }

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

Explanation:

• The PriorityQueueWithSortedList class maintains a sorted list of key-value pairs, where the keys represent the priority levels and the values represent the elements.
• The Enqueue method adds an element to the priority queue with the specified priority.
• The Dequeue method removes and returns the element with the highest priority.
• The Peek method returns the element with the highest priority without removing it.
• The Count property returns the number of elements in the priority queue.

This implementation ensures that elements are processed in ascending order of priority, with the highest priority elements processed first.

• Priority Queue with SortedDictionary:

Another way to implement a priority queue in C# is by using a SortedDictionary<TKey, TValue>. Similar to the sorted list implementation, the keys in the SortedDictionary represent the priority levels, and the values represent the elements of the priority queue.

using System;
using System.Collections.Generic;

public class PriorityQueueWithSortedDictionary<TPriority, TValue> where TPriority : IComparable
{
    private SortedDictionary<TPriority, Queue<TValue>> sortedDictionary;

    public PriorityQueueWithSortedDictionary()
    {
        sortedDictionary = new SortedDictionary<TPriority, Queue<TValue>>();
    }

    public void Enqueue(TPriority priority, TValue value)
    {
        if (!sortedDictionary.ContainsKey(priority))
        {
            sortedDictionary[priority] = new Queue<TValue>();
        }

        sortedDictionary[priority].Enqueue(value);
    }

    public TValue Dequeue()
    {
        if (sortedDictionary.Count == 0)
        {
            throw new InvalidOperationException("The priority queue is empty.");
        }

        var priority = sortedDictionary.Keys.Min();
        var value = sortedDictionary[priority].Dequeue();

        if (sortedDictionary[priority].Count == 0)
        {
            sortedDictionary.Remove(priority);
        }

        return value;
    }

    public TValue Peek()
    {
        if (sortedDictionary.Count == 0)
        {
            throw new InvalidOperationException("The priority queue is empty.");
        }

        var priority = sortedDictionary.Keys.Min();
        return sortedDictionary[priority].Peek();
    }

    public int Count
    {
        get { return sortedDictionary.Values.Sum(queue => queue.Count); }
    }
}

Explanation:

• The PriorityQueueWithSortedDictionary class maintains a sorted dictionary of queues, where the keys represent the priority levels, and the values represent queues containing elements with the same priority.
• The Enqueue method adds an element to the priority queue with the specified priority.
• The Dequeue method removes and returns the element with the highest priority.
• The Peek method returns the element with the highest priority without removing it.
• The Count property returns the number of elements in the priority queue.

This implementation ensures that elements are processed in ascending order of priority, with the highest priority elements processed first.

Custom Priority Queue Implementation

• Designing the Priority Queue Class:

When designing a custom priority queue class, it’s essential to consider the underlying data structure and the operations required for efficient priority queue management. The class should encapsulate the data and functionality related to priority queue operations while providing a clear and intuitive interface for interacting with the queue.

public class PriorityQueue<T>
{
    private List<T> items;
    private Func<T, T, bool> comparer;

    public PriorityQueue(Func<T, T, bool> compareFunction)
    {
        items = new List<T>();
        comparer = compareFunction;
    }

    public void Enqueue(T item)
    {
        items.Add(item);
        items.Sort((x, y) => comparer(x, y) ? -1 : 1);
    }

    public T Dequeue()
    {
        if (items.Count == 0)
        {
            throw new InvalidOperationException("The priority queue is empty.");
        }

        var item = items[0];
        items.RemoveAt(0);
        return item;
    }

    public T Peek()
    {
        if (items.Count == 0)
        {
            throw new InvalidOperationException("The priority queue is empty.");
        }

        return items[0];
    }

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

Explanation:

• The PriorityQueue class encapsulates a list of items and a comparison function to determine the priority order.
• The Enqueue method adds an item to the priority queue and sorts the items based on the comparison function.
• The Dequeue method removes and returns the item with the highest priority.
• The Peek method returns the item with the highest priority without removing it.
• The Count property returns the number of items in the priority queue.

This custom priority queue implementation allows flexibility in defining the priority order based on the comparison function provided by the user.

• Defining Priority Queue Operations:

When defining priority queue operations, it’s essential to consider the core functionalities required for efficient task management and data processing. Priority queue operations typically include enqueueing elements with specified priorities, dequeuing elements with the highest priority, and peeking at the element with the highest priority without removing it. Additionally, operations for checking the number of elements in the priority queue and handling edge cases such as queue underflow and overflow are crucial for ensuring the reliability and robustness of the priority queue implementation.

public class PriorityQueue<T>
{
    private List<T> items;
    private Func<T, T, bool> comparer;

    public PriorityQueue(Func<T, T, bool> compareFunction)
    {
        items = new List<T>();
        comparer = compareFunction;
    }

    public void Enqueue(T item)
    {
        items.Add(item);
        items.Sort((x, y) => comparer(x, y) ? -1 : 1);
    }

    public T Dequeue()
    {
        if (items.Count == 0)
        {
            throw new InvalidOperationException("The priority queue is empty.");
        }

        var item = items[0];
        items.RemoveAt(0);
        return item;
    }

    public T Peek()
    {
        if (items.Count == 0)
        {
            throw new InvalidOperationException("The priority queue is empty.");
        }

        return items[0];
    }
}

Explanation:

• The Enqueue method adds an item to the priority queue and sorts the items based on the comparison function provided during initialization. The comparison function determines the priority order of elements.
• The Dequeue method removes and returns the item with the highest priority from the priority queue.
• The Peek method returns the item with the highest priority without removing it from the priority queue.

What if elements in a priority queue have equal priority?

If elements in a priority queue have equal priority, the behavior depends on the specific implementation and the underlying data structure used. Here are some common scenarios:

1. Random selection: Some priority queue implementations may choose to dequeue elements with equal priority randomly. This approach prevents biases and ensures that all elements with the same priority have an equal chance of being processed next.
2. Custom tie-breaking criteria: In certain applications, a tie-breaking criterion may be defined to resolve conflicts when elements have equal priority. For example, elements with the same priority may be further prioritized based on additional attributes such as their unique identifiers, timestamps, or some other criteria.
3. Implementation-specific behavior: The behavior of a priority queue with equal-priority elements may vary depending on the specific implementation details and the choice of underlying data structure.

Here’s a code example demonstrating how you can handle equal-priority elements in a priority queue using C#

using System;
using System.Collections.Generic;

public class PriorityQueue<T>
{
    private SortedDictionary<int, Queue<T>> priorityQueue;

    public PriorityQueue()
    {
        priorityQueue = new SortedDictionary<int, Queue<T>>();
    }

    public void Enqueue(int priority, T item)
    {
        if (!priorityQueue.ContainsKey(priority))
        {
            priorityQueue[priority] = new Queue<T>();
        }

        priorityQueue[priority].Enqueue(item);
    }

    public T Dequeue()
    {
        if (priorityQueue.Count == 0)
        {
            throw new InvalidOperationException("The priority queue is empty.");
        }

        var highestPriority = priorityQueue.Keys.Min();
        var item = priorityQueue[highestPriority].Dequeue();

        if (priorityQueue[highestPriority].Count == 0)
        {
            priorityQueue.Remove(highestPriority);
        }

        return item;
    }

    public T Peek()
    {
        if (priorityQueue.Count == 0)
        {
            throw new InvalidOperationException("The priority queue is empty.");
        }

        var highestPriority = priorityQueue.Keys.Min();
        return priorityQueue[highestPriority].Peek();
    }
}

Priority Queue Operations and Algorithms

Enqueue Operation

The enqueue operation in a priority queue adds an element to the queue while maintaining the priority order. When implementing the enqueue operation, it’s essential to insert the new element at the appropriate position in the queue based on its priority compared to existing elements.

public void Enqueue(T item)
{
    items.Add(item);
    items.Sort((x, y) => comparer(x, y) ? -1 : 1);
}

Explanation:

• The Enqueue method adds the specified item to the priority queue.
• The items.Sort method is used to sort the items based on the comparison function provided during initialization.
• The comparison function determines the priority order of elements. If the comparison function returns true, it indicates that the first element should come before the second element in the sorted order, and vice versa.

Dequeue Operation

The dequeue operation removes and returns the element with the highest priority from the priority queue. This operation ensures that the highest priority element is processed first, following the priority order defined by the comparison function.

public T Dequeue()
{
    if (items.Count == 0)
    {
        throw new InvalidOperationException("The priority queue is empty.");
    }

    var item = items[0];
    items.RemoveAt(0);
    return item;
}

Explanation:

• The Dequeue method removes and returns the first element (element with the highest priority) from the priority queue.
• If the priority queue is empty, an InvalidOperationException is thrown to indicate that the dequeue operation cannot be performed on an empty queue.

Peek Operation

The peek operation allows you to view the element with the highest priority in the priority queue without removing it. This operation is useful for inspecting the next element to be dequeued without altering the queue’s state.

public T Peek()
{
    if (items.Count == 0)
    {
        throw new InvalidOperationException("The priority queue is empty.");
    }

    return items[0];
}

Explanation:

• The Peek method returns the first element (element with the highest priority) from the priority queue without removing it.
• If the priority queue is empty, an InvalidOperationException is thrown to indicate that the peek operation cannot be performed on an empty queue.

Priority Updates and Modifications

Priority updates and modifications involve changing the priority of elements already present in the priority queue. This operation requires careful consideration, as it may involve reordering elements to maintain the priority order.

public void UpdatePriority(T item, T newPriority)
{
    if (!items.Contains(item))
    {
        throw new ArgumentException("The item does not exist in the priority queue.");
    }

    items.Remove(item);
    Enqueue(newPriority, item);
}

Explanation:

• The UpdatePriority method allows you to update the priority of an existing item in the priority queue.
• If the item does not exist in the priority queue, an ArgumentException is thrown.
• The method removes the item from the priority queue and then enqueues it again with the new priority.

Priority Queue Sorting Algorithms (Heap-based, Binary Search Tree-based)

Priority queues can be implemented using various sorting algorithms, such as heap-based or binary search tree-based implementations. These algorithms offer different trade-offs in terms of time complexity, space complexity, and performance characteristics, allowing you to choose the most suitable implementation based on your specific requirements and constraints.

Heap-based Priority Queue:

public class HeapPriorityQueue<T>
{
    private List<T> heap;
    private Func<T, T, bool> comparer;

    public HeapPriorityQueue(Func<T, T, bool> compareFunction)
    {
        heap = new List<T>();
        comparer = compareFunction;
    }

    public void Enqueue(T item)
    {
        heap.Add(item);
        HeapifyUp(heap.Count - 1);
    }

    public T Dequeue()
    {
        if (heap.Count == 0)
        {
            throw new InvalidOperationException("The priority queue is empty.");
        }

        T item = heap[0];
        heap[0] = heap[heap.Count - 1];
        heap.RemoveAt(heap.Count - 1);
        HeapifyDown(0);
        return item;
    }

    private void HeapifyUp(int index)
    {
        while (index > 0)
        {
            int parentIndex = (index - 1) / 2;
            if (comparer(heap[index], heap[parentIndex]))
            {
                Swap(index, parentIndex);
                index = parentIndex;
            }
            else
            {
                break;
            }
        }
    }

    private void HeapifyDown(int index)
    {
        while (true)
        {
            int leftChildIndex = 2 * index + 1;
            int rightChildIndex = 2 * index + 2;
            int smallestChildIndex = index;

            if (leftChildIndex < heap.Count && comparer(heap[leftChildIndex], heap[smallestChildIndex]))
            {
                smallestChildIndex = leftChildIndex;
            }

            if (rightChildIndex < heap.Count && comparer(heap[rightChildIndex], heap[smallestChildIndex]))
            {
                smallestChildIndex = rightChildIndex;
            }

            if (smallestChildIndex != index)
            {
                Swap(index, smallestChildIndex);
                index = smallestChildIndex;
            }
            else
            {
                break;
            }
        }
    }

    private void Swap(int index1, int index2)
    {
        T temp = heap[index1];
        heap[index1] = heap[index2];
        heap[index2] = temp;
    }
}

Explanation:

• The HeapPriorityQueue class maintains a list representing a binary heap, where each element in the list corresponds to a node in the heap.
• The Enqueue method adds a new element to the priority queue and ensures that the heap property is maintained by performing a “heapify up” operation.
• The Dequeue method removes and returns the root element of the heap (which has the highest priority) and ensures that the heap property is maintained by performing a “heapify down” operation.
• The HeapifyUp and HeapifyDown methods are responsible for restoring the heap property after adding or removing elements, respectively.
• The Swap method is used to swap elements in the heap during heapify operations.

Binary Search Tree-based Priority Queue:

public class BinarySearchTreePriorityQueue<T> where T : IComparable<T>
{
    private TreeNode root;

    private class TreeNode
    {
        public T Value { get; }
        public TreeNode Left { get; set; }
        public TreeNode Right { get; set; }

        public TreeNode(T value)
        {
            Value = value;
        }
    }

    public void Enqueue(T item)
    {
        root = Insert(root, item);
    }

    private TreeNode Insert(TreeNode node, T item)
    {
        if (node == null)
        {
            return new TreeNode(item);
        }

        if (item.CompareTo(node.Value) < 0)
        {
            node.Left = Insert(node.Left, item);
        }
        else
        {
            node.Right = Insert(node.Right, item);
        }

        return node;
    }

    public T Dequeue()
    {
        if (root == null)
        {
            throw new InvalidOperationException("The priority queue is empty.");
        }

        T min = FindMin(root);
        root = DeleteMin(root);
        return min;
    }

    private T FindMin(TreeNode node)
    {
        while (node.Left != null)
        {
            node = node.Left;
        }

        return node.Value;
    }

    private TreeNode DeleteMin(TreeNode node)
    {
        if (node.Left == null)
        {
            return node.Right;
        }

        node.Left = DeleteMin(node.Left);
        return node;
    }
}

Explanation:

• The BinarySearchTreePriorityQueue class maintains a binary search tree, where each node contains an element of the priority queue.
• The Enqueue method inserts a new element into the binary search tree while maintaining the binary search tree property.
• The Dequeue method removes and returns the smallest element in the binary search tree (which has the highest priority) by finding the minimum value in the tree and deleting the corresponding node.
• The Insert, FindMin, and DeleteMin methods are responsible for inserting, finding the minimum value, and deleting the minimum value from the binary search tree, respectively.

We provide insightful content and resources to empower developers on their coding journey. If you found this content helpful, be sure to explore more of our materials for in-depth insights into various Programming Concepts.

Also check out(Our Data Structures Series in C#):

• How to Implement Queue in C#?

Stay tuned for future articles and tutorials that illustrate complex topics, helping you become a more proficient and confident developer.