Priority Queue Before .NET 6

Overview

Before .NET 6 was released, C# doesn’t have Priority Queue built-in library. There is no alternative to substitute this data structure.

SortedList looks potential as Priority Queue substitute, but it won’t work because:

It doesn’t allow duplicate elements
The Add and RemoveAt/Remove operations have O(n) time complexity which is worse than Enqueue and Dequeue operations that has O(log n) time complexity

Therefore, C# developer has to create their own Priority Queue data structure from the scratch.

Priority Queue Implementation

Priority Queue typically uses Heap as the underlying data structure, thus all operations here will be based on Heap operations such as Heapify.

The current implementation is not generic, so it assumes all elements are integer and it uses Max-Heap.

Complete Code

public class PriorityQueue
{
    public List<int> Queue { get; }

    public PriorityQueue()
    {
        Queue = new List<int>();
    }

    public void Insert(int element)
    {
        Queue.Add(element);
        int currentIndex = Queue.Count - 1;
        while (currentIndex > 0 
            && ElementAtCurrentPositionLessThanParentElement(currentIndex))
        {
            Swap(currentIndex, (currentIndex - 1) / 2);

            currentIndex = (currentIndex - 1) / 2;
        }
    }

    public int Poll()
    {
        int temp = Queue[0];
        Queue[0] = Queue[Queue.Count - 1];
        Queue[Queue.Count - 1] = temp;

        int maxElement = Queue[Queue.Count - 1];
        Queue.RemoveAt(Queue.Count - 1);

        Heapify(0);

        return maxElement;
    }

    private void Heapify(int index)
    {
        int largestElementIndex = index;
        int leftChildIndex = index * 2 + 1;
        int rightChildIndex = index * 2 + 2;

        if (leftChildIndex < Queue.Count 
            && Queue[leftChildIndex] > Queue[largestElementIndex])
        {
            largestElementIndex = leftChildIndex;
        }

        if (rightChildIndex < Queue.Count 
            && Queue[rightChildIndex] > Queue[largestElementIndex])
        {
            largestElementIndex = rightChildIndex;
        }

        if (largestElementIndex != index)
        {
            Swap(index, largestElementIndex);
            Heapify(largestElementIndex);
        }
    }

    private bool ElementAtCurrentPositionLessThanParentElement(int currentIndex)
    {
        return Queue[currentIndex] > Queue[(currentIndex - 1) / 2];
    }

    private void Swap(int i, int j)
    {
        int temp = Queue[j];
        Queue[j] = Queue[i];
        Queue[i] = temp;
    }
}

Priority Queue Before .NET 6

Overview#

Priority Queue Implementation#

Complete Code#

Overview

Priority Queue Implementation

Complete Code