Generic Heap Implementation in C#

Question

This has been done a thousand times on here already, but here's another binary heap implementation. The implementation is generic in terms of heap elements, allows for injection of any type of comparison strategy via the constructor, and has an extra internal lookup scheme to achieve element removal in O(log(n)) time.

I am looking for overall tips to better utilize the (C#) language, design ideas to improve the structure/performance of this class, or any other feedback. Thanks!

using System;
using System.Collections.Generic;
using System.Linq;

namespace GenericHeap
{
    /// <summary>
    /// A generic heap implementation that allows injection of custom comparison strategies for 
    /// determining element priority
    /// </summary>
    /// <typeparam name="T">Type of element that will be stored in the heap</typeparam>
    public class Heap<T> where T : IComparable
    {
        /// <summary>
        /// The heap's internal elements
        /// </summary>
        protected readonly List<T> elements;

        /// <summary>
        /// A lookup for mapping each heap element value/instance to one or more indices in the internal array
        /// </summary>
        protected readonly Dictionary<T, HashSet<int>> elementIndexLookup;

        private readonly IComparer<T> comparer;

        /// <summary>
        /// Returns true if there are no elements in the heap, otherwise returns false
        /// </summary>
        public bool IsEmpty => elements.Count == 0;

        /// <summary>
        /// Returns the number of elements in the heap
        /// </summary>
        public int Count => elements.Count;

        /// <summary>
        /// Constructs a <see cref="Heap{T}"/> with default comparer for type <see cref="T"/>
        /// </summary>
        public Heap() : this(Comparer<T>.Default)
        {
        }

        /// <summary>
        /// Constructs a <see cref="Heap{T}"/> with custom comparer for type <see cref="T"/>
        /// </summary>
        /// <param name="comparer">The custom comparer to use when determining priority order</param>
        public Heap(IComparer<T> comparer)
        {
            this.comparer = comparer;
            this.elements = new List<T>();
            this.elementIndexLookup = new Dictionary<T, HashSet<int>>();
        }

        /// <summary>
        /// Removes the highest priority element from the heap and returns it to the caller of <see cref="Poll"/>
        /// </summary>
        /// <returns>The highest priority element</returns>
        /// <exception cref="InvalidOperationException">Thrown when there are no elements in the heap</exception>
        public T Poll()
        {
            if (this.IsEmpty)
            {
                throw new InvalidOperationException("There are no elements in the heap to poll");
            }

            var rootIndex = 0;
            var lastElementIndex = this.elements.Count - 1;
            var root = this.elements[rootIndex];

            this.elements[rootIndex] = this.elements[lastElementIndex];
            this.elements.RemoveAt(lastElementIndex);

            this.BubbleDown(rootIndex);

            return root;
        }

        /// <summary>
        /// Inserts an element into the heap
        /// </summary>
        /// <param name="newElement">The element to insert</param>
        public void Insert(T newElement)
        {
            this.elements.Add(newElement);
            var lastIndex = this.elements.Count - 1;
            this.AddIndexToLookup(newElement, lastIndex);

            this.BubbleUp(this.elements.Count - 1);
        }

        /// <summary>
        /// Gets the highest priority element from the heap without removing it
        /// </summary>
        /// <returns>The highest priority element</returns>
        /// <exception cref="InvalidOperationException">Thrown when there are no elements in the heap</exception>
        public T Peek()
        {
            if (this.IsEmpty)
            {
                throw new InvalidOperationException("There are no elements in the heap to peek");
            }

            return this.elements[0];
        }

        /// <summary>
        /// Checks if an element exists in the heap
        /// </summary>
        /// <param name="element">The element to search for</param>
        /// <returns>True if element exists in the heap, otherwise false</returns>
        /// <remarks>
        /// This method is an O(1) operation due to the usage of an internal element lookup
        /// </remarks>
        public bool Contains(T element)
        {
            return this.elementIndexLookup.ContainsKey(element);
        }

        /// <summary>
        /// Removes the first instance of <paramref name="elementToRemove"/> found in the heap
        /// </summary>
        /// <param name="elementToRemove">The element to remove from the heap</param>
        /// <remarks>
        /// This method is an O(log(n)) operation due to the usage of an internal lookup for
        /// identifying element indices
        /// </remarks>
        /// <exception cref="ArgumentException">Thrown when <paramref name="elementToRemove"/> does not exist in the heap</exception>
        public void Remove(T elementToRemove)
        {
            if (!this.elementIndexLookup.ContainsKey(elementToRemove))
            {
                throw new ArgumentException("Element does not exist in the heap");
            }

            var index = this.elementIndexLookup[elementToRemove].First();
            var lastIndex = this.elements.Count - 1;

            this.SwapElements(index, lastIndex);
            this.RemoveIndexFromLookup(this.elements[lastIndex], lastIndex);
            this.elements.RemoveAt(lastIndex);
            this.BubbleDown(index);
        }

        private void BubbleDown(int parentIndex)
        {
            var leftChildIndex = this.GetIndexOfLeftChild(parentIndex);
            var rightChildIndex = this.GetIndexOfRightChild(parentIndex);
            var maxIndex = this.elements.Count - 1;

            if (leftChildIndex > maxIndex)
            {
                return;
            }

            if (rightChildIndex > maxIndex)
            {
                if (this.IsChildHigherPriority(parentIndex, leftChildIndex))
                {
                    this.SwapElements(parentIndex, leftChildIndex);
                }

                return;
            }

            var highestPriorityElementIndex = this.GetHighestPriorityElementIndex(parentIndex, leftChildIndex, rightChildIndex);

            if (highestPriorityElementIndex == parentIndex)
            {
                return;
            }

            this.SwapElements(parentIndex, highestPriorityElementIndex);
            this.BubbleDown(highestPriorityElementIndex);
        }

        private void BubbleUp(int childIndex)
        {
            if (childIndex == 0)
            {
                return;
            }

            var parentIndex = this.GetParentIndex(childIndex);

            if (IsChildHigherPriority(parentIndex, childIndex))
            {
                this.SwapElements(parentIndex, childIndex);
                this.BubbleUp(parentIndex);
            }
        }

        private bool IsChildHigherPriority(int parentIndex, int childIndex)
        {
            return this.comparer.Compare(this.elements[childIndex], this.elements[parentIndex]) > 0;
        }

        private int GetHighestPriorityElementIndex(int parentIndex, int leftChildIndex, int rightChildIndex)
        {
            var isLeftChildHigherPriority = this.IsChildHigherPriority(parentIndex, leftChildIndex);
            var isRightChildHigherPriority = this.IsChildHigherPriority(parentIndex, rightChildIndex);

            if (isLeftChildHigherPriority && isRightChildHigherPriority)
            {
                return this.GetHigherPriorityElementIndex(leftChildIndex, rightChildIndex);
            }
            else if (isLeftChildHigherPriority)
            {
                return leftChildIndex;
            }
            else if (isRightChildHigherPriority)
            {
                return rightChildIndex;
            }

            return parentIndex;
        }

        private int GetHigherPriorityElementIndex(int leftElementIndex, int rightElementIndex)
        {
            if (this.comparer.Compare(this.elements[leftElementIndex], this.elements[rightElementIndex]) > 0)
            {
                return leftElementIndex;
            }
            else
            {
                return rightElementIndex;
            }
        }

        private void SwapElements(int firstIndex, int secondIndex)
        {
            if (firstIndex == secondIndex)
            {
                return;
            }

            var firstElement = this.elements[firstIndex];
            var secondElement = this.elements[secondIndex];
            this.elements[firstIndex] = secondElement;
            this.elements[secondIndex] = firstElement;

            this.RemoveIndexFromLookup(firstElement, firstIndex);
            this.RemoveIndexFromLookup(secondElement, secondIndex);

            this.AddIndexToLookup(this.elements[firstIndex], firstIndex);
            this.AddIndexToLookup(this.elements[secondIndex], secondIndex);
        }

        private void RemoveIndexFromLookup(T element, int index)
        {
            this.elementIndexLookup[element].Remove(index);
        }

        private void AddIndexToLookup(T element, int index)
        {
            if (this.elementIndexLookup.ContainsKey(element))
            {
                this.elementIndexLookup[element].Add(index);
            }
            else
            {
                this.elementIndexLookup.Add(element, new HashSet<int> { index });
            }
        }

        private int GetParentIndex(int childIndex)
        {
            if (childIndex % 2 == 0)
            {
                return (childIndex - 2) / 2;
            }
            else
            {
                return (childIndex - 1) / 2;
            }
        }

        private int GetIndexOfLeftChild(int currentIndex)
        {
            return 2 * currentIndex + 1;
        }

        private int GetIndexOfRightChild(int currentIndex)
        {
            return 2 * currentIndex + 2;
        }
    }
}
```

Answer 1

I like the idea of the elementIndexLookup but you should be aware of the following:

  private void RemoveIndexFromLookup(T element, int index)
  {
    this.elementIndexLookup[element].Remove(index);
  }

When you remove the last index from an elements lookup entry, you should remove the entry from elementIndexLookup else this:

  public bool Contains(T element)
  {
    return this.elementIndexLookup.ContainsKey(element);
  }

will be wrong if elementIndexLookup[element].Count == 0

and this:

var index = this.elementIndexLookup[elementToRemove].First();

will fail with an exception.

---

This

  private void AddIndexToLookup(T element, int index)
  {
    if (this.elementIndexLookup.ContainsKey(element))
    {
      this.elementIndexLookup[element].Add(index);
    }
    else
    {
      this.elementIndexLookup.Add(element, new HashSet<int> { index });
    }
  }

can be simplified to:

  private void AddIndexToLookup(T element, int index)
  {
    if (!elementIndexLookup.TryGetValue(element, out var indices))
      elementIndexLookup[element] = indices = new HashSet<int>();

    indices.Add(index);
  }

Answer 2

• The code in question is easy to read and understand.
• You have named your variables and methods well, using the recommended naming and casing styles.
• The code in question is well documented as well.
• You are using braces {} althought they might be optional which is good because it prevents hidden and therfor hard to find bugs.

That had been the good news about your code, now we talk about the bad news, but fortunately there aren't any, at least I don't see any.

What bothers me a little and what I wouldn't do is using the this keyword that extensively all over the class.
The this keyword is usually used to distinguish methods parameters from local variables/fields. One don't use it everywhere and for sure one shouldn't use it for calling methods.

If you don't plan to inherit/extend this class I don't see any sense for declaring elements and elementIndexLookup as protected. Usually one should choose composition over inheritance.

Answer 3

Nice Code!

One simple suggestion. Add a constructor with capacity and initialize the List with that capacity. If you don't have the capacity preinitialize everytime you Add a new element to the list it has to do a resize and that has a time complexity of O(N) so you are losing the O(log N).

Answer 4

Small non-C# side note from me: The code seems over-documented.

Properties like elements, Count or IsEmpty don't need a documentation, in my opinion. They are self-explanatory.

Answer 5

This function can be simplified:

private int GetParentIndex(int childIndex)
{
    if (childIndex % 2 == 0)
    {
        return (childIndex - 2) / 2;
    }
    else
    {
        return (childIndex - 1) / 2;
    }
}

This implementation explicitly takes care to divide only even numbers by two, but there is no problem dividing an odd number by two, that will round towards zero. In the case that childIndex is even, (childIndex - 1) / 2 would still work. Hypothetically there would be a difference if childIndex is even and non-positive, but that means the parent of the root is being calculated (which does not happen, BubbleUp stops at the root) or that an invalid index (negative) is passed in which would be a bug elsewhere.

Or to summarize, the implementation could be:

private int GetParentIndex(int childIndex)
{
    return (childIndex - 1) / 2;
}