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?
- the Priority Queue contains only k elements, so adding/removing items takes O(log(k)), where k << N;
- 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)}"); }