Let me start by saying, I myself am struggling to find the appropriate data structure to implement Heap based algorithms using C# as a preferred language. There are 3rd party implementations but obviously you cant use them on Leetcode. Also, I am not sure if it is feasible to try to implement Heap class in a 45 min interview.

I just want to put down all the information that I found during my research and hopefully we all collectively can come up with some kind of workaround. (It feels like there are very few C# devs compared to Java & Python devs)

First of all, the million dollar question - Why ain't there any datastructure in dotnet which implements Heap. To be frank - I could not find anything which satisfactorily answers the question.

There has been recommendation to implement it. There are arguments towards it and there are counter arguments against implementing it but bottom line is that it has not been implemented.

https://github.com/dotnet/runtime/issues/14032

My research led me to look into SortedDictionary, SortedList & SortedSet. I started reading into this article - https://medium.com/@lifei.8886196/sorted-data-structure-in-c-an-introduction-to-sorteddictionary-sortedlist-and-sortedset-19a69fe184e0

Internally SortedDictionary is implemented as BST (Binary search tree) & SortedSet is implemented as Red black tree. SortedList does not even come close to being an alternative

I was basing my hopes on First property in SortedDictionary & Min \ Max property in SortedSet. Very quickly my research vanquished my hopes.

https://github.com/dotnet/runtime/issues/18668

First property in SortedDictionary is not native. It comes from Linq and for that internally it first does GetEnumerator. Unlike in MinHeap where getting min elements in O(1), getting First in SortedDictionary is O(logn). It needs to travel from root of the BST to the leftmost child in the tree which is the minimum element.

Min \ Max property in SortedSet also take O(logn) time. Source code for SortedSet reveals that both the properties call Red-Black Tree traversal. Min property returns left most child where as Max property returns right most child from the tree (travesing from the root of the tree).

I almost feel like you have to go with SortedDictionary assuming its heap and hope that your interview does not know much of C# or otherwise be upfront about it and ask them if you can assume this to be a heap for the sake of the algorithm problem (and hope that they dont mind it)

Please let me know if any of you have faced the same problem and what did you do?

Is memorizing & writing the whole Heap class in an interview even a possible option?

Update (13th Feb 2021) - Courtsey @akashsax14

Good info. There finally seems to be some movement (after 5 years of discussion) for getting PQ added to C# Collections : https://github.com/dotnet/runtime/pull/46009