MinHeap implementation

Question

Please comment on this.

class MinHeap<T> where T: IComparable
    {
        List<T> elements;

        public MinHeap()
        {
            elements = new List<T>();
        }

        public void Add(T item)
        {
            elements.Add(item);
            Heapify();
        }

        public void Delete(T item)
        {
            int i = elements.IndexOf(item);
            int last = elements.Count - 1;

            elements[i] = elements[last];
            elements.RemoveAt(last);
            Heapify();
        }

        public T PopMin()
        {
            if (elements.Count > 0)
            {
                T item = elements[0];
                Delete(item);
                return item;
            }
            //relook at this - should we just throw exception?
            return default(T);
        }

        public void Heapify()
        {
            for (int i = elements.Count - 1; i > 0; i--)
            {                
                int parentPosition = (i+1) / 2 - 1;
                parentPosition = parentPosition >= 0 ? parentPosition : 0;

                if (elements[parentPosition].CompareTo(elements[i])>1)
                {
                    T tmp = elements[parentPosition];
                    elements[parentPosition] = elements[i];
                    elements[i] = tmp;
                }
            }
        }
    }

Answer 1

• You should always try to program against an interface instead of against an implementation.

  List<T> elements;
  

  should be

  IList<T> elements;  
  

• Restrict the scope of fields and methods to the smallest possible.
  So public void Heapify() should be private instead.

• The swapping of elements inside the Heapify() method can be extracted to a private method.

  private void SwapElements(int firstIndex, int secondIndex)
  {
      T tmp = elements[firstIndex];
      elements[firstIndex] = elements[secondIndex];
      elements[secondIndex] = tmp;
  }  
  

  Former Heapify() method now

  private void Heapify()
  {
      for (int i = elements.Count - 1; i > 0; i--)
      {                
          int parentPosition = (i+1) / 2 - 1;
          parentPosition = parentPosition >= 0 ? parentPosition : 0;
  
          if (elements[parentPosition].CompareTo(elements[i]) > 1)
          {
              SwapElements(parentPosition, i)
          }
      }
  } 
  

• Potential bug
  You are checking if the CompareTo() method returns a value > 1 but you miss ==1 as the documentation states

  • value < 0 => This instance precedes obj in the sort order.
  • value == 0 => This instance occurs in the same position in the sort order as obj.
  • value > 0 => This instance follows obj in the sort order.

• //relook at this - should we just throw exception?
  If you want to simulate a Stack then you should throw an InvalidOperationException but only if you also provide a property Count so that a user of your class can evaluate if he can call PopMin safely.

Answer 2

Some of your operations are slow for a Binary Heap.

Every time an item is added or deleted, you're checking every item in the list to see if it's in the proper order. This is O(n) time. Insertion and deletion on binary heaps can be done in O(log(n)) time by checking only if certain elements need to be swapped.

When inserting an element, just check the added item and its parent. If they are out of order, swap them and check the added item again. Continue this until the added item and its parent are in proper order. Check the Heap operations section of the Binary heap article on Wikipedia for more info.

Answer 3

Two things:

1. This is very important, and I wasn't able to properly declare an instance of my class without it. You have to add <T> after IComparable:

   class MinHeap<T> where T : IComparable<T>
   

2. The suggestion of changing List to IList was an interesting thought. However, the reason you'd want to use List is because it automatically resizes its capacity as it grows in size. IList does not have this functionality, at least from what I've read. You would want to use IList if you are deriving another class from it (e.g. class MyList<T> : IList<T>) and want to modify the behavior of the List directly.

So, my final implementation came out to this:

class MinHeap<T> where T : IComparable<T>
{
    List<T> elements;
    ...
}

class Node : IComparable<Node>
{
    ...
}

void MyFunction()
{
    Node currNode;
    MinHeap<Node> nodeHeap = new MinHeap<Node>(1000);   //Capacity
    ...
}

Answer 4

this comment is about the structure, not about the methods, in your implementation of the MinHeap. In my opinion, using an array instead of a linked list to implement the Heap seems to be a better choice because accessing the elements is \$O(1)\$ using the array, there is no need for traversal, which is not the case if a List is used.