Priority Queue in .NET 6

NET Framework 6 adds the long-awaited Priority Queue to the list of collections. 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.

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;
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)}");          
}