C# 10 PriorityQueue is here !
.NET 6 and C# 10 has finally arrived in the past November
and brought with it tons of new cool features and optimization improvements.
Some of the mentionable are:
- Minimal APIs: Creating a new ASP.NET Core app with just a few lines of code using a simplified hosting model.
- Async streaming: Asynchronously stream data from the server without any need for buffering.
- Null-state analysis: All ASP.NET Core templates now have C# null-state analysis enabled by default.
One of the features is the praised PriorityQueue class that was missing in C# for 20 years.
although the lack of PriorityQueue class didn’t stop developers from implementing their PriorityQueue class, having an inbuilt class like this makes things a bit more official and easier.
What Is A Priority Queue?
Well, a Priority Queue is a type of data structure that holds a collection of Elements (values) of some type, and each item is enqueued with an associated priority that determines the dequeue order.
Elements with the lowest priority are dequeued first.
even though we have “Queue” in the name, the PriorityQueue type does not guarantee first-in-first-out (FIFO) semantics for elements of equal priority.
Priority queues are used in graph problems, trees problems, scheduling tasks, Bandwidth management, and more.
Behind the scenes, Microsoft uses an array to manage the priority queue
priority queues can be used as min\max heaps as they consist of the same principles.
By default Min Heap is implemented by this class but this could be changed by providing a different comparer.
In min heaps, every element is smaller than the elements below them.
In max heaps, every element is larger than the elements below them.
Every new element inserted, is inserted into the next empty spot, looking top to bottom, left to right,
So assuming we know every level of the binary tree is full, except for the last one, we can get a specific element, parent, children, and height based on the index on the array. with this implementation, the min\max element would always appear as the first element in the array. which makes getting the min element in constant time.
Though when we dequeue\enqueue elements, we want to “heapify” the heap to make the heap valid once again, which is moving the element to the next element (top to bottom, left to right) and swapping it with its parents until the element is in its right place.
How To Use A Priority Queue?
The usage is pretty simple,
PriorityQueue<TElement,TPriority> accept two types of classes
TElement is the type of element
and TPriority is the type of priority.
when choosing a priority type, make sure it has a default comparer or a comparer that you’ve implemented.
In this example, we initialize a priority queue of string elements with integers as a priority,
by default, the PriorityQueue sorts the items in ascending order, (minimum first).
The output of this program is as follows:
John Lennon born in 1940
Ringo Starr3 born in 1940
Ringo Starr2 born in 1940
Ringo Starr1 born in 1940
Paul McCartney born in 1942
George Harrison born in 1943Process finished with exit code 0.
this is a great example of showing why the priority queue is not organized as FIFO; as we can see both John Lennon and Ringo Starr(1\2\3) are born in 1940, but we do not get them in the order of insertion.
How To Use A Custom Comparer?
The PriorityQueue class has a constructor that accepts a comparer object.
more specifically, an IComparer<TPriority>
So for example if we would like to simulate a max heap we would provide a different comparer:
CompareTo under the hood is comparing the current item to the provided item, if the first one is larger, we will return -1
if the second one is larger we will return 1
and if they are equal, we return 0.
//actual IL code:
public int CompareTo(int value)
{
if (m_value < value) return -1;
if (m_value > value) return 1;
return 0;
}we could easily implement some custom Comparator for other types of classes based on the same logic.
As expected the output is:
George Harrison born in 1943
Paul McCartney born in 1942
Ringo Starr2 born in 1940
Ringo Starr1 born in 1940
Ringo Starr3 born in 1940
John Lennon born in 1940Process finished with exit code 0.
LeetCode!
To conclude this article we’ll use the priority queue class to solve a simple LeetCode question.
(2) Kth Largest Element in an Array — LeetCode
Given an integer array
numsand an integerk, return thekthlargest element in the array.Note that it is the
kthlargest element in the sorted order, not thekthdistinct element.
of course, we could sort the array and run K times to get the element,
this would be in O(N log N) whereas N is the number of elements in the array
and a constant Space complexity (ignoring the space needed to sort the array).
but we could use less time with a space trade-off to get the element using a min-heap.
For every number that appears in the nums array, we are throwing that into the heap, but whenever the heap size exceeds K we’re going to pop the min element from that heap,
which ultimately keeps the K Largest elements in that heap so by the time we get to the end of our loop, the top of the heap will be our desired number.
For example, runtime logs:
iteration 1 (3, 3) Count =1
iteration 2 (2, 2) (3, 3) Count = 2
iteration 3 (1, 1) (3, 3) (2, 2) Count = 3 → after dequeue min (3, 3) (2, 2)
iteration 4 (2, 2) (3, 3) (5, 5) Count = 3 → after dequeue min (3, 3) (5, 5)
iteration 5 (3, 3) (5, 5) (6, 6) Count = 3 → after dequeue min (5, 5) (6, 6)
iteration 6 (4, 4) (6, 6) (5, 5) Count = 3 → after dequeue min (6, 6) (5, 5)
pq.Peek() will return the min element in that heap, in that case it is (5, 5)
this solution works in time complexity of O(N * Log K) and Space complexity of O(K)
if you got to this part of this article, I want to say thank you for reading, and I hope it has been a useful post for you.
Thanks for giving me motivation for learning more and more :)
