I needed min-heap in C# for my experiment with Sudoku solving A* and surprisingly I didn't find it in .NET environment. There were some implementations available online, but far less then I expected. Heap is such a basic data structure, I expected an overwhelming amount of implementations in C# for various school projects or such. I just implemented it myself. Initially I only wanted to implement min-heap but later it evolved into a project of it's own. And I still wonder, why my projects last so long, if they are lucky enough to be finished at all.
TL;DR: here is GitHub repository of Blitva , a tiny collection of C# tools, which includes described heap implementations. This is MIT licensed . You can use it any way you want.
Basic data container is realized by ArrayList, the .NET's built-in dynamic array. I didn't want to go all the way into resizing space, copying and all that comes with implementing own dynamic array. Data is stored in base class named Ahnentafel, because it only implements storage and index manipulations. In ahnentafel list it is easy to implement binary tree which I needed for heap. Beside getting parent and children of any node in O(1), it also does some basic operations on data container: check if it is empty, clear and count.
It is inherited into Heap<T> class, that stores binary tree in list format, not only because it is easy, but also because it is fast. Heap<T> class was extracted later, after I had already written MinHeap<T>, just because I was looking at finished code and found so many stuff I could reuse for additional MaxHeap<T> class that it felt wrong not to do it. In Heap<T> there is an entire implementation of both MinHeap and MaxHeap.
The only functional difference is in bubbling down and up where it is important to know whether it is maximum or minimum heap. In first case, bigger elements should bubble up, in latter smaller elements should bubble up. To distinguish between the two I added enum HeapType that must be given already at the time of construction. That prevents any Heap<T> object to remain with undefined behavior.
Generic type T in Heap is forced to be IComparable, because otherwise it would be hard to generically implement comparisons between stored items and that is a prerequisite operation if heap property is to be preserved. Some operations on basic data is handled in Heap class and some in it's parent, the Ahnentafel class. For each one I was considering whether something is heap specific operation or could also be used in other binary trees in the future that might want to use ahnentafel list as a basis, but convenience was also considered.
MinHeap and MaxHeap are only wrappers of Heap class. You could just as well use generic Heap class instead and do great. It does however improve readability of the code and lessen the chances to make mistake. MaxHeap sets Heap to be maxHeap type automatically and implements functions named -Max. MinHeap does likewise. New -Max and -Min functions only call getBest, extractBest, etc, but make it harder to forget what type of heap was used at some particular part of the code. It is also easier for programming because if an object is of type MinHeap, for instance, even the IntelliSense will give you a clue you should not try to call getMax on it.
What came later started as a joke. A coworker of mine suggested I should implement mid-heap too. We laughed to the idea a bit, but I was thinking it could really mean something :) If minimum and maximum heap maintain minimum and maximum values at all times, available for lookup in O(1), couldn't the definition of medium heap be median maintenance? MidHeap could return median in O(1) and I already have all the required pieces :) For this I needed two heaps, minimum and maximum. If new number that is to be inserted is bigger then the smallest in minHeap, it should go there, else it goes into maxHeap. After that I only needed to maintain them both equally large and I have it: median available in O(1), the so called "MidHeap"! :)
MidHeap<T> class therefore needs two different heaps and it would be great if that strange class' base would be of type Heap, but that would give him own data storage that it wouldn't use. Because of that I made it inherit MinHeap and only include maxHeap as a class member. That way I can have my cake and eat it too, but the tradeoff was the code readability is worse then it could have been. Because it is a strange type of Heap it needed isEmpty, getCount and clear functions rewritten to include both heaps at the same time. That was done in a bit ugly way, by hiding original implementations with "new" keyword, but if I wanted to do it correctly, by declaring MinHeap or Heap functions virtual, base class MinHeap implementation would have called MidHeap's functions, which is bad, because they are also needed for it's own operations.
Anyway, here is my contribution to the fairly modest number of C# heap implementations available on the web.
Previous:
How I implemented language aware web scraper
Next:
Beginner's view on Python