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 PriorityQueue type for ages. Let’s see how would they look written in C# on .net 6:

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

K Closest Points to Origin

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…