First of all, congrats to everybody! .net 6 has been released.
Since the very beginning, .NET Framework has been missing a natively supported Heap data structure. Obviously, we do not need this data structure in our every day coding routine, however, this has been limitation factor for the C# language, for example on the online programming learning platforms like LeetCode. In addition, C# has always been down-prioritized as a language of choise for the coding interviews, partly because of lacking this type.
Heaps are tree-based data structures and are crucial in several efficient graph algorithms such as Dijkstra’s algorithm or for the Top ‘K’ problems.
And finally now, with .net 6 release there is a System.Collections.Generic.PriorityQueue<,>
type implementation of the heap data structure.
Syntax
The implemented syntax for the PriorityQueue
in .net is not very typical I would say, as it maintains the TPriority
type which can be basically anything. And therefore, you must provide the priority value on every .Enqueue()
method call. The most valuable methods (and their approximate time complexity) for us are the following:
.Enqueue(TElement, TPriority)
O(log K).Dequeue()
O(log K).Peek()
O(1)- .
Count
O(1)
Also, the heaps can be of two types : Min heap and Max heap
In order to define the min
or the max heap
, we need to manipulate with the Comparer
object that we can provide for the PriorityQueue
constructor. For example, for Int32
priority type the min and max heap comparer implementations would look like the following:
public class MaxHeapInt32Comparer : IComparer<int>
{
public int Compare(int x, int y)
{
return y - x;
}
}
public class MinHeapInt32Comparer : IComparer<int>
{
public int Compare(int x, int y)
{
return x - y;
}
}
Examples
Here is a nice post about Top ‘K’ elements problems with their implementations in Java which has had the . Let’s see how would they look written in C# on .net 6:PriorityQueue
type for ages
Kth Largest Element in an Array
public int FindKthLargest(int[] nums, int k)
{
// Create a min heap
var minHeap = new PriorityQueue<int, int>(new MinHeapInt32Comparer());
// Insert the array elements into the min heap.
for (int i = 0; i < nums.Length; i++)
{
minHeap.Enqueue(nums[i], nums[i]);
// Pop out the root element if the min heap size is larger than k
if (minHeap.Count > k)
{
minHeap.Dequeue();
}
}
return minHeap.Peek();
}
public int[][] KClosest(int[][] points, int k)
{
// Create a max heap
var maxHeap = new PriorityQueue<int[], int>(new MaxHeapInt32Comparer());
// Custom priority function (ignoring the Math.Sqrt calculation)
var getDistanceToOrigin = (int[] point) => point[0] * point[0] + point[1] * point[1];
// Traverse and insert points to the max heap
foreach (var point in points)
{
maxHeap.Enqueue(point, getDistanceToOrigin(point));
// Pop out the root element if the max heap size is larger than K
if (maxHeap.Count > k)
{
maxHeap.Dequeue();
}
}
// Extract closest points into an array
var res = new List<int[]>();
while (maxHeap.Count > 0) res.Add(maxHeap.Dequeue());
return res.ToArray();
}
Looks good enough to me, however, if you might have noticed, last lines about extracting all elements are resulting into O(K log K)
time complexity. Would be nice to have a method in the PriorityQueue
that would get all the elements (even ignoring the ordering) in at least O(K)
time.
Waiting for the LeetCode to enable .net 6 as a runtime for C# language…