Binary heap implementation with a generic base class

Question

This is my attempt at implementing a Binary heap. I made an abstract base class Heap with an abstract property controlling whether it is a min-heap or a max-heap.

One thing I've been struggling with was which collections.generic interfaces to apply to the class. Enumerating the heap only makes a bit of sense. At the same time, it is a collection, but I'm not sure if all the interface methods really make sense for a Heap. So any pointers for that would be welcome.

Abstract Heap<T>

  public abstract class Heap<T> : IEnumerable<T>, ICollection<T> where T : IComparable {
    private T[] innerT;
    private int capacity = 1;
    private int numberOfLevels = 1;

    public int Count { get; private set; } = 0;

    public bool IsReadOnly => false;

    protected abstract bool CloserToRoot(int comparison);

    public Heap() {
      innerT = new T[capacity];
    }

    public Heap(int capacity) {
      innerT = new T[capacity];
      this.capacity = capacity;
      this.numberOfLevels = CapacityToLevels(capacity);
    }

    public Heap(IEnumerable<T> sequence) {
      if (sequence == null) {
        throw new ArgumentNullException(nameof(sequence));
      }

      foreach (var item in sequence) {
        Add(item);
      }
    }

    public void Add(T item) {
      Count++;
      if (Count == capacity) {
        Resize();
      }

      innerT[Count - 1] = item;
      UpHeap();
    }

    private int Find(T item) {
      return FindInternal(item, 0);
    }

    private int FindInternal(T item, int index) {
      if (index >= Count) {
        return -1; // end of the heap.
      }
      var comp = innerT[index].CompareTo(item);
      if (comp == 0) { // Found it!
        return index;
      } else if (CloserToRoot(comp)) { // Still possible to be lower.
        var rightChild = IndexToRightChildNode(index);
        var leftChild = rightChild - 1;
        var rightResult = FindInternal(item, rightChild);
        var leftResult = FindInternal(item, leftChild);
        if (rightResult >= 0) {
          return rightResult;
        }
        if (leftResult >= 0) {
          return leftResult;
        }
      }
      return -1; // Nope :( Either both children were -1 or this index has a value lower than item;
    }




    private void UpHeap() {
      var currentNode = Count - 1;
      var parentNode = IndexToParentNode(currentNode);
      while (currentNode != 0 && CloserToRoot(innerT[currentNode].CompareTo(innerT[parentNode]))) {
        Swap(currentNode, parentNode);
        currentNode = parentNode;
        parentNode = IndexToParentNode(currentNode);
      }
    }

    private void DownHeap(int startingIndex) {
      int currentIndex;
      var largestIndex = startingIndex;
      do {
        currentIndex = largestIndex;
        var rightChild = IndexToRightChildNode(currentIndex);
        var leftChild = rightChild - 1;

        if (leftChild < Count && CloserToRoot(innerT[leftChild].CompareTo(innerT[largestIndex]))) {
          largestIndex = leftChild;
        }

        if (rightChild < Count && CloserToRoot(innerT[rightChild].CompareTo(innerT[largestIndex]))) {
          largestIndex = rightChild;
        }

        Swap(largestIndex, currentIndex);
      } while (largestIndex != currentIndex);

    }

    private void Swap(int a, int b) {
      var placeholder = innerT[a];
      innerT[a] = innerT[b];
      innerT[b] = placeholder;
    }

    private static int CapacityToLevels(int capacity) {
      var Log2 = Math.Log(2);
      return (int)Math.Ceiling(Math.Log(capacity + 1) / Log2);
    }

    private static int IndexToRightChildNode(int index) {
      return 2 * index + 2;
    }

    private static int IndexToParentNode(int index) {
      return (index - 1) / 2;
    }



    private void Resize() {
      capacity = capacity << 1 | 1;
      numberOfLevels++;
      Array.Resize(ref innerT, capacity);
    }

    public IEnumerator<T> GetEnumerator() {
      return (IEnumerator<T>)innerT.GetEnumerator();
    }

    IEnumerator IEnumerable.GetEnumerator() {
      return innerT.GetEnumerator();
    }

    public void Clear() {
      capacity = 1;
      numberOfLevels = 1;
      innerT = new T[capacity];
    }

    public bool Contains(T item) {
      return Find(item) != -1;
    }

    public void CopyTo(T[] array, int arrayIndex) {
      if (arrayIndex < 0 || arrayIndex >= Count) {
        throw new ArgumentOutOfRangeException(nameof(arrayIndex));
      }
      innerT.CopyTo(array, arrayIndex);
    }

    public bool Remove(T item) {
      var index = Find(item);
      if (index == -1) {
        return false;
      }
      innerT[index] = default(T);
      Swap(index, Count - 1);
      Count--;
      DownHeap(index);
      return true;
    }
  }

MaxHeap

  public class MaxHeap<T> : Heap<T> where T : IComparable {
    public MaxHeap() {
    }

    public MaxHeap(int capacity) : base(capacity) {
    }

    public MaxHeap(IEnumerable<T> sequence) : base(sequence) {
    }

    protected override bool CloserToRoot(int comparison) => comparison > 0;
  }

MinHeap

  public class MinHeap<T> : Heap<T> where T : IComparable {
    public MinHeap() {
    }

    public MinHeap(int capacity) : base(capacity) {
    }

    public MinHeap(IEnumerable<T> sequence) : base(sequence) {
    }

    protected override bool CloserToRoot(int comparison) => comparison < 0;
  }

Answer 1

Design considerations

• The main purpose of a heap is to provide quick access to the top-most item, so I'd expect to see some kind of Peek and Pop methods, allowing for usage like while (heap.Count > 0) { DoWork(heap.Pop()); }. Surprisingly, such methods are absent.
• While a heap is some kind of collection, and implementing IEnumerable<T> does let you use Linq and other enumerable-consuming methods, that's not really using a heap for what it does best. If you do need to enumerate it, then perhaps you're better off using a different data-structure in the first place?
• Instead of relying on inheritance and requiring T to implement IComparable (or IComparable<T>), consider letting the user pass in a Func<T, T, int> or an IComparer<T>. This should be more flexible, allowing for usage like new Heap<PaymentRequest>((a, b) => a.DueDate.CompareTo(b.DueDate));, where PaymentRequest either doesn't implement IComparable, or does but in an unsuitable way (such as comparing payment amounts rather than due-dates). Also, instead of creating a separate class you now only need to create a separate method (or lambda).

Bugs

• The Heap(IEnumerable<T> sequence) constructor fails to initialize innerT when the given sequence is empty. This breaks enumeration.
• The Heap(int capacity) constructor allows a capacity of 0, but it'll cause Add to fail with an IndexOutOfRange. Use >= instead of == when comparing count and capacity.
• IEnumerator<T> GetEnumerator fails with an InvalidCastException. You can fix this by casting innerT to IEnumerable<T>, to ensure that IEnumerable<T>.GetEnumerator is called instead of IEnumerable.GetEnumerator. But see the next point:
• GetEnumerator and CopyTo do not take into account that Count can be smaller than capacity, resulting in additional 'empty' values being enumerated or copied.
• CopyTo is not implemented correctly: the index parameter in Array.CopyTo is a destination index, not a source index. This means that the arrayIndex >= Count check makes no sense: it should be arrayIndex + Count > array.Length.

Other notes

• When dealing with multiple constructors, try designating one as the 'main' constructor and let the others call it. In this case, Heap(int capacity) would be a good choice: Heap() : this(1), Heap(IEnumerable<T> sequence) : this(1).
• The current implementation of GetEnumerator doesn't take situations into account where the heap is modified while being enumerated. I'm not sure whether it's worth preventing that, but it's something to be aware of.
• FindInternal:
  • can be optimized by first checking the result of FindInternal(item, rightChild). If that's a match then there's no need to search throught the left subtree.
  • is only used by Find, so it could be made an inner method.
  • its readability can be improved by adding a bit of whitespace between the first early-out check and the rest of the method. Also, personally I tend to omit braces for if-statements that only have a single break/continue/return/throw statement. I'm aware of the risks but I don't think it's worth the additional clutter in these particular cases.
• DownHeap performs an unnecessary swap when largestIndex == currentIndex.
• Instead of just adding each item, there's apparently a more efficient algorithm (Floyd's) for building heaps from a given sequence.
• Resize:
  • would be more accurately named as ResizeToNextLevel.
  • can be made more reusable by adding an int newCapacity parameter, allowing you to reuse it in both the constructors and the Clear method.
  • is a little bit inconsistent in that it uses bitwise-operators, while all other utility methods use arithmetic operators.
• capacity is always equal to innerT.Length, so I would make it a property instead: private int capacity => innerT.Length;.
• To me, CloserToRoot(a.CompareTo(b)) isn't easily comprehensible. If it returns true, does that mean that a should be higher-up the tree than b, or the other way around?
• Similarly, UpHeap and DownHeap are, at least to me, not immediately descriptive names. Adding an int addedIndex parameter to UpHeap and renaming the startingIndex parameter in DownHeap to removedIndex should help to make their purpose a little more obvious. Some documentation wouldn't be a bad thing either.
• Some index variables are clearly named as such (startingIndex, currentIndex, and so on) but others are not (leftChild, rightChild, currentNode, parentNode and so on). Personally I would use the index suffix everywhere, but whatever you choose, try to be consistent.
• Public, private and static methods are somewhat mixed. Try grouping related methods together.

Answer 2

I don't see much to improve from algorithmic point of view. So I will focus on Object Oriented design.

1. How about doing it similarly to Sort method? I mean instead of making abstract method, try just injecting Comparator into generic Heap implementation.

2. People are generally scary of long and complex code. It would be nicer to try to split it into smaller parts:

   • First (most general) concept is to extract each huge operation (like Find, Downheap etc) into separate class with appropriate Single Responsibility. They usually accept in constructor original method parameters, hold its internal state as fields instead of local variables.
     
     They can also accept in constructor reference to original object but it would be even better design practice to extract internal Heap state into even smaller object and avoid circular dependency.
     
     Another approach is to make those classes stateless (just moving methods into separate classes and injecting Heap internal state)
   • Second idea would be to separate defensive programming from actual algorithms to make them cleaner and more readable (I would suggest to move them into a class mentioned in point 3. or into separate Facade responsible for validating user input)
   • You can also extract single steps of DownHeap and UpHeap routines into separate methods.
3. You mentioned, that you struggled a little bit with collections.generic interfaces. My proposed solution would be not to pollute actual implementation but instead use Adapter Design Pattern

4. Another thing that comes into mind (beside OO) is to calculate numberOfLevels from either Count or capacity (using ceiled logarithm)

As #harold mentioned in comment it is probably unused

5. You can simplify main body of the find routine:

   var rightResult = FindInternal(item, IndexToRightChildNode(index));
   var leftResult = FindInternal(item, IndexToLeftChildNode(index));
   return rightResult >= 0 ? rightResult : leftResult;
   

Please notice that in your case when neither rightResult nor leftResult has value greather than 0, the function will return -1 anyway.

6. (Optionally, as applied in example of 5) You can add a an arrow functionIndexToLeftChildNode for completeness or to increase readability when you decide to inline some variables.

7. You can extract common (utility) subroutine from DownHeap:

   private int UpdateLargestIndex(int currentLargestIndex, int childIndex) {
     if (childIndex < Count && CloserToRoot(innerT[childIndex].CompareTo(innerT[currentLargestIndex]))) {
       return childIndex;
     }
     return currentLargestIndex;
   }