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;
 }
 }
 }
 }

• Peter Kiss: If this is in production code you should consider using SortedSet<T> (msdn.microsoft.com/en-us/library/dd412070(v=vs.110).aspx)
• Aadith Ramia: @Peter Did you mean SortedSet in place of the List my class encapsulates or as a replacement to my implementation itself?
• Peter Kiss: As a complete replacement of your class. One thing is not implemented in the SortedSet is the PopMin() method. The SortedSet only implements Peek functionality.
• Lee: In the Heapify method you have int parentPosition = (i+1) / 2 - 1; but this seems wrong to me. As an example, the elements at index 6 and 7 both belong to the parent at index 3. Your formula results in 2 for index 6 and 3 for index 7 ((6+1) / 2 - 1, 7 / 2 - 1, 3 - 1, 2 and (7+1) / 2 - 1, 8 / 2 - 1, 4 - 1, 3). The formula seems like it should instead be int parentPosition = i / 2; instead (6 / 2 = 3 and 7 / 2 = 3). This is of course assuming integer division.
• Aadith Ramia: @Lee, both input and output are 0-based. 6th and 7th positions would have indices 5 and 6 respectively and their parent position's index as computed by the used expression would be 2 which corresponds to 3rd element. I know this can be easily confusing.

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.

• Xiaoy312: Can you explain the reason behind the first point, favoring interface over implementation?

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.

• Aadith Ramia: Agreed from a performance standpoint. In this case, it was essential to allow dynamic expansion. Hence the list.
• Peter Ruderman: List<T> is not a linked list.