HiveBrain v1.2.0
Get Started
← Back to all entries
patterncsharpMinor

Min & Max heap implementation

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
minimplementationmaxheap

Problem

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) = 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

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

return Nodes[0];
}

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

Solution

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).

Code Snippets

public abstract class AbstractHeap
{
    #region internal properties
    private int Capacity { get; set; }
    internal int Size { get; set; }
    internal int[] Nodes { get; set; }
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)];
    }
internal abstract void heapifyUp();
    internal abstract void heapifyDown();

Context

StackExchange Code Review Q#162311, answer score: 8

Revisions (0)

No revisions yet.