Priority Queue in .NET 6

Priority Queue is a data structure in computer science that is used to manage a collection of prioritized elements. It allows adding, removing and peeking (reading) elements in the order of their priority. The priority queue is used in many applications such as job scheduling, network routing, data compression, and more. .NET 6, the latest version of the .NET framework, introduces a new Priority Queue data structure. In this blog post, we will discuss the Priority Queue in .NET 6, its features, and how it can be used.

An example of usage of Priority Queues is getting the k-highest value in an array without sorting the array: the algorithm is keeps k values in the Priority Queue, the root node being the lowest of them, and removes lower values when the size of the queue exceeds k; after processing the input array, the root node of the Priority Queue will be the k-highest value of the array.

A priority queue is typically implemented using a heap data structure. A heap is a binary tree where each node has a priority that is greater than or equal to the priorities of its children. The highest priority element is always stored at the root of the heap, making it easy to retrieve. When an element is added to the heap, it is inserted at the bottom of the tree and then “bubbled up” to its correct position by comparing its priority to that of its parent. When an element is removed from the heap, the root element is removed and then “bubbled down” to its correct position by comparing its priority to that of its children.

If inserting or removing an element in a Priority Queue takes O(log(N)), and sorting the array would take O(N log(N)), why is worth it?

1. the Priority Queue contains only k elements, so adding/removing items takes O(log(k)), where k << N, so using a priority queue reduces the time complexity of the algorithm to O(n log k), which is much more efficient than sorting the entire collection;
2. peeking at the lowest value in the Priority Queue is O(1), so comparing the new value with the lowest value already in the queue is an early-exit optimization that skips altering the contents of the queue.

Here is an implementation of the k-highest algorithm using Priority Queues:

public class KBiggestFinderNET6<T>
{
    public T Find(List<T> items, int position)
    {
        // priority and value of the item in the priority queue is the same
        PriorityQueue<T, T> queue = new PriorityQueue<T, T>();
 
        foreach (T currentItem in items)
        {
            // if the priority queue already has position items, check if the new item is higher than the 
            // lowest item in the priority queue before adding it, if not early exit
            if ((queue.Count <= position) || (Operator.GreaterThan<T>(currentItem, queue.Peek())))
            {
                queue.Enqueue(currentItem, currentItem);
                // keep the length of the priority queue equal to position, so that the root item in the priority
                // queue is the the one to return
                while (queue.Count > position)
                    queue.Dequeue();
            }
        }
 
        return queue.Peek();
    }
}

Comparing the results of the code above with sorting the input array proves that the results are matching:

static void Main(string[] args)
{            
    var finder = new KBiggestFinderNET6<int>();
 
    List<int> items = new List<int> { 5, 4, 10, 7, 1, 3, 8, 1, 2, 9 };
    var sorted_items = new List<int>(items);
    sorted_items.Sort();
    sorted_items.Reverse();
 
    for (int position = 1; position <= items.Count; position++)
        Console.WriteLine($"Position {position}: list is {sorted_items[position - 1]}, found value is {finder.Find(items, position)}");          
}

In conclusion, the Priority Queue in .NET 6 is a powerful data structure that can be used to efficiently retrieve the k highest values from a collection of elements. By understanding how it works and how it is used in the k-highest values algorithm, developers can leverage this tool to optimize their applications and improve performance.