A heap is a balanced tree which has some special properties. There are two variations of heap: MinHeap and MaxHeap. In a MinHeap, the root node is lesser than all the child nodes. MaxHeap has the maximum value in the root node.

Heap is not available in the .NET framework. The best implementation that I could find for a MinHeap is a blog post from Allan. The purpose of a MinHeap is to retrieve the minimum value after adhoc inserts into the collection. Accordingly, MinHeap should have the following minimum operations:

The implementation of MinHeap should ensure that the minimum value is retrieved in O(logN) time. The below code shows the implementation:

Both the Insert and ExtractMin operations execute in O(logN) time. The base of log is the number of child nodes that every node contains. To get a faster ExtractMin operation, the number of child nodes can be increased. Below is a console application to test the MinHeap implementation.

Popping out the minimum element in a MinHeap (one by one) will give the elements in a sorted ascending order. The algorithm is called HeapSort and runs in O(N logN) time.

MinHeap implementation for .NET
Tagged on: