Min & Max heap implementation

Question

As follows I have implemented Min and Max heap data structure, using an array for storing elements. I would need a code review, please. Please, spare recommendations for generic implementation as they are not useful in my current requirements. I have written down units tests and I'm sharing those, too.

Abstract Class

public abstract class AbstractHeap
{
    #region internal properties
    private int Capacity { get; set; }
    internal int Size { get; set; }
    internal int[] Nodes { get; set; }
    #endregion

    #region constructors
    public AbstractHeap()
    {
        Capacity = 100;
        Size = 0;
        Nodes = new int[Capacity];
    }
    #endregion

    #region helperMethods
    public void EnlargeIfNeeded()
    {
        if (Size == Capacity)
        {
            Capacity = 2 * Capacity;
            Array.Copy(Nodes, Nodes, Capacity);
        }
    }

    public int getLeftChildIndex(int parentIndex)
    {
        return 2 * parentIndex + 1;
    }

    public bool hasLeftChild(int parentIndex)
    {
        return getLeftChildIndex(parentIndex) < Size;
    }

    public int leftChild(int index)
    {
        return Nodes[getLeftChildIndex(index)];
    }

    public int getRightChildIndex(int parentIndex)
    {
        return 2 * parentIndex + 2;
    }

    public bool hasRightChild(int parentIndex)
    {
        return getRightChildIndex(parentIndex) < Size;
    }

    public int rightChild(int index)
    {
        return Nodes[getRightChildIndex(index)];
    }

    public int getParentIndex(int childIndex)
    {
        return (childIndex - 1) / 2;
    }

    public bool hasParent(int childIndex)
    {
        return getParentIndex(childIndex) >= 0;
    }

    public int parent(int index)
    {
        return Nodes[getParentIndex(index)];
    }

    public void swap(int index1, int index2)
    {
        int temp = Nodes[index1];
        Nodes[index1] = Nodes[index2];
        Nodes[index2] = temp;
    }

    #endregion

    #region available public methods

    /// <summary>
    /// Gets the minimum element at the root of the tree
    /// </summary>
    /// <returns>Int value of minimum element</returns>
    /// <exception cref="">InvalidOperationException when heap is empty</exception>
    public int peek()
    {
        if (Size == 0)
            throw new InvalidOperationException("Heap is empty");

        return Nodes[0];
    }

    /// <summary>
    /// Removes the minimum element at the root of the tree
    /// </summary>
    /// <returns>Int value of minimum element</returns>
    /// <exception cref="">InvalidOperationException when heap is empty</exception>
    public int pop()
    {
        if (Size == 0)
            throw new InvalidOperationException("Heap is empty");

        int item = Nodes[0];
        Nodes[0] = Nodes[Size - 1];
        Size--;
        heapifyDown();
        return item;
    }

    /// <summary>
    /// Add a new item to heap, enlarging the array if needed
    /// </summary>
    /// <returns>void</returns>
    public void add(int item)
    {
        EnlargeIfNeeded();
        Nodes[Size] = item;
        Size++;
        heapifyUp();
    }
    #endregion

    #region abstract methods
    internal abstract void heapifyUp();
    internal abstract void heapifyDown();
    #endregion
}

Max Heap implementation using abstract class

public class MaxHeap : AbstractHeap
{
    #region constructors

    public MaxHeap() : base()
    {
    }
    #endregion

    #region internal methods
    internal override void heapifyDown()
    {
        int index = 0;
        while (hasLeftChild(index))
        {
            int largerChildIndex = getLeftChildIndex(index);
            if (hasRightChild(index) && rightChild(index) > leftChild(index))
            {
                largerChildIndex = getRightChildIndex(index);
            }

            if (Nodes[largerChildIndex] > Nodes[index])
                swap(index, largerChildIndex);
            else
                break;
            index = largerChildIndex;
        }
    }
    internal override void heapifyUp()
    {
        int index = Size - 1;

        while (hasParent(index) && parent(index) < Nodes[index])
        {
            swap(index, getParentIndex(index));
            index = getParentIndex(index);
        }
    }
    #endregion
}

Min Heap implementation using abstract class

public class MinHeap : AbstractHeap
{
    #region constructors
    public MinHeap() : base()
    {
    }
    #endregion

    #region internal methods
    internal override void heapifyDown()
    {
        int index = 0;
        while (hasLeftChild(index))
        {
            int smallerChildIndex = getLeftChildIndex(index);
            if (hasRightChild(index) && rightChild(index) < leftChild(index))
            {
                smallerChildIndex = getRightChildIndex(index);
            }

            if (Nodes[smallerChildIndex] < Nodes[index])
                swap(index, smallerChildIndex);
            else
                break;
            index = smallerChildIndex;
        }
    }
    internal override void heapifyUp()
    {
        int index = Size - 1;

        while (hasParent(index) && parent(index) > Nodes[index])
        {
            swap(index, getParentIndex(index));
            index = getParentIndex(index);
        }
    }
    #endregion
}

Unit tests for max heap

[TestClass]
public class MaxHeapTests
{
    [TestMethod]
    public void AddEmptyRemove()
    {
        var heap = new MaxHeap();

        heap.add(10);
        Assert.AreEqual(10, heap.peek());

        int result = heap.pop();
        Assert.AreEqual(10, result);
        heap.add(20);
        Assert.AreEqual(20, heap.peek());
    }

    [TestMethod]
    public void AddMultipleCheckPeek()
    {
        var heap = new MaxHeap();
        foreach (int item in new int[] { 10, 20, 2, 45, 7, 5, 12 })
            heap.add(item);
        Assert.AreEqual(heap.peek(), 45);
    }

    [TestMethod]
    public void AddMultipleCheckPopThenPeek()
    {
        var heap = new MaxHeap();
        foreach (int item in new int[] { 10, 20, 2, 45, 7, 5, 12 })
            heap.add(item);
        int result = heap.pop();
        Assert.AreEqual(45, result);
        Assert.AreEqual(20, heap.peek());
    }

    [TestMethod]
    [ExpectedException(typeof(InvalidOperationException))]
    public void PeekPoopEmpty()
    {
        var heap = new MaxHeap();
        heap.peek();
        heap.pop();
    }
}

Unit tests for min heap

[TestClass]
public class MinHeapTests
{
    [TestMethod]
    public void AddEmptyRemove()
    {
        var heap = new MinHeap();

        heap.add(10);
        Assert.AreEqual(10, heap.peek());

        int result = heap.pop();
        Assert.AreEqual(10, result);
        heap.add(20);
        Assert.AreEqual(20, heap.peek());
    }

    [TestMethod]
    public void AddMultipleCheckPeek()
    {
        var heap = new MinHeap();
        foreach (int item in new int[] { 10, 20, 2, 45, 7, 5, 12 })
            heap.add(item);
        Assert.AreEqual(heap.peek(), 2);
    }

    [TestMethod]
    public void AddMultipleCheckPopThenPeek()
    {
        var heap = new MinHeap();
        foreach (int item in new int[] { 10, 20, 2, 45, 7, 5, 12 })
            heap.add(item);
        int result = heap.pop();
        Assert.AreEqual(2, result);
        Assert.AreEqual(5, heap.peek());
    }

    [TestMethod]
    [ExpectedException(typeof(InvalidOperationException))]
    public void PeekPoopEmpty()
    {
        var heap = new MinHeap();
        heap.peek();
        heap.pop();
    }
}

Answer 1

public abstract class AbstractHeap
{
    #region internal properties
    private int Capacity { get; set; }
    internal int Size { get; set; }
    internal int[] Nodes { get; set; }

Capacity doesn't seem to serve any purpose at all. It just mirrors Nodes.Length and is a potential source of bugs.

Why should subclasses be able to access the setters of Size and Nodes? I think they should be private.

---

    public void EnlargeIfNeeded()
    {
        if (Size == Capacity)
        {
            Capacity = 2 * Capacity;
            Array.Copy(Nodes, Nodes, Capacity);
        }
    }

This is buggy. Add a unit test which inserts more than 100 elements into a heap, watch it turn red, and then fix it.

---

    public int getLeftChildIndex(int parentIndex)
    {
        return 2 * parentIndex + 1;
    }

    public bool hasLeftChild(int parentIndex)
    {
        return getLeftChildIndex(parentIndex) < Size;
    }

    public int leftChild(int index)
    {
        return Nodes[getLeftChildIndex(index)];
    }

Is there any particular reason for not using expression-valued methods?

Is there any particular reason for not following standard C# style and using UpperCamelCase for the method names?

To me it seems a bit overkill to have three methods for each of left, right, and parent, but that's a question of style and I can see an argument that it's for readability of the upheap and downheap methods. On the other hand, why are all of these methods (and Swap) public? That's exposing far too much of the internal implementation.

---

    internal abstract void heapifyUp();
    internal abstract void heapifyDown();

I really can't understand why these methods, which are the most complicated ones in the whole class, should be implemented twice. I would much rather implement them once, in the base class, and handle the differences by means of an IComparer field or an abstract method Compare(int a, int b).

Answer 2

I will just repeat my comment - I don't see a point of creating Min and Max Heap functionalities at the same time. MaxHeap data structure can be made by using MinHeap taking all numbers with negative sign. As result there is no point to use abstract class AbstractHeap unless you are not going to use it for another class.

Also I think it is worth to mention that there is one modification of the heap data structure that allows FindMin as well as FindMax with \$\mathcal{O}(1)\$ time.

---

You described a few helper methods, but all of them are public. I don't think that is necessary.

---

Accordingly to the Capitalization Conventions you should capitalize the first letter of public methods.

---

There is a redundancy of constructors - in your case, one constructor in abstract class AbstractHeap is enough.

Also public abstract constructor doesn't make any sense. The protectedaccess modifier better fits in this case.

---

Your TestMethods are not extensive enough. Instead of current implementation of AddMultipleCheckPeek and AddMultipleCheckPopThenPeek I would suggest to go through all possible permutations of input array.

[TestMethod]
public void AddMultipleCheckPeek() {
    foreach (int[] a in GetAllPermutations(new[]{ 10, 20, 2, 45, 7, 5, 12 })) {
        MinHeap heap = new MinHeap();
        foreach (int i in a) {
            heap.Add(i);
        }
        Assert.AreEqual(heap.Peek(), a.Min());
    }
}

[TestMethod]
public void AddMultipleCheckPopThenPeek() {
    foreach (int[] a in GetAllPermutations(new[] { 10, 20, 2, 45, 7, 5, 12 })) {
        MinHeap heap = new MinHeap();
        foreach (int i in a) {
            heap.Add(i);
        }
        foreach (int i in a.OrderBy(x => x)) {
            Assert.AreEqual(heap.Peek(), i);
            Assert.AreEqual(heap.Pop(), i);
        }
    }
}

private static IEnumerable<int[]> GetAllPermutations(int[] a) {
    Array.Sort(a);
    yield return a;
    while (true) {
        int i = a.Length - 2;
        while (a[i] > a[i + 1] && i != 0) {
            i--;
        }
        if (i == 0) {
            yield break;
        }
        int k = a.Length - 1;
        while (a[k] < a[i]) {
            k--;
        }
        Swap(a, i, k);
        for (int j = i + 1; j <= (a.Length + i) / 2; j++) {
            Swap(a, j, a.Length + i - j);
        }
        yield return a;
    }
}

The GetAllPermutations method is not optimal, but I provided it just for completeness of the example (the code is translated from a source code of GSL' permutation_next function).