MinHeap implementation for .NET

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:

interface IMinHeap<T>
{
    // Should run in O(logN)
    void Insert(T value);
    // Should run in O(logN)
    T ExtractMin();
}

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

class MinHeap<T> : IMinHeap<T> where T : IComparable<T>
{
    private List<T> _heap;
    private static readonly int NodeCount = 2;
    private static readonly int BufferSize = 10000;

    public void Heapify(T[] values)
    {
        // Not the correct implementation of Heapify
        // Heapify should run in O(N)
        // The below Heapify runs in O(N*log(N))
        _heap = new List<T>(values.Length + BufferSize);

        for (int index = 0; index < values.Length; index++)
        {
            T value = values[index];
            Insert(value);
        }
    }


    public void Insert(T value)
    {
        _heap.Add(value);
        
        if (_heap.Capacity == _heap.Count)
            _heap.Capacity += BufferSize;

        BubbleUp(_heap.Count - 1);
    }


    public T ExtractMin()
    {
        if (_heap.Count == 0)
            return default(T);

        T min = _heap[0];
        _heap[0] = _heap[_heap.Count - 1];
        _heap.RemoveAt(_heap.Count - 1);
        if (_heap.Count > 0)
            BubbleDown(0);
        return min;
    }

    void BubbleUp(int nodeIndex)
    {
        if (nodeIndex != 0)
        {
            int parentIndex = GetParentIndex(nodeIndex);
            var node = _heap[nodeIndex];
            var parentNode = _heap[parentIndex];
            if (parentNode.CompareTo(node) > 0)
            {
                Swap(nodeIndex, parentIndex);
                BubbleUp(parentIndex);
            }
        }
    }

    void BubbleDown(int nodeIndex)
    {
        var node = _heap[nodeIndex];
        int startIndex = GetChildStartIndex(nodeIndex);
        if (startIndex < _heap.Count)
        {
            int endIndex = Math.Min(GetChildEndIndex(nodeIndex),
&nbsp;                                   _heap.Count - 1);
            int minIndex = startIndex;
            for (int index = startIndex + 1; 
                 index <= endIndex; 
                 index++)
            {
                if (_heap[index].CompareTo(_heap[minIndex]) < 0)
                {
                    minIndex = index;
                }
            }

            if (node.CompareTo(_heap[minIndex]) > 0)
            {
                Swap(minIndex, nodeIndex);
                BubbleDown(minIndex);
            }
        }
    }

    void Swap(int node1, int node2)
    {
        var tmpNode = _heap[node1];
        _heap[node1] = _heap[node2];
        _heap[node2] = tmpNode;
    }

    int GetParentIndex(int index)
    {
        return (int)Math.Ceiling((decimal)index / NodeCount) - 1;
    }

    int GetChildStartIndex(int index)
    {
        return index * NodeCount + 1;
    }

    int GetChildEndIndex(int index)
    {
        return index * NodeCount + NodeCount;
    }
}

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.

static void Main(string[] args)
{
    var heap = new MinHeap<int>();
    var numbers = Enumerable.Range(1, 6).Reverse().ToArray();
    heap.Heapify(numbers);
    int min;
    do
    {
        min = heap.ExtractMin();
        Console.WriteLine("Minimum is {0}", min);
    }
    while (min != 0);
    Console.ReadKey();
}

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.

Related Posts

Leave a Reply

Your email address will not be published.