11
\$\begingroup\$

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;
        }
    }
}
```
\$\endgroup\$
  • 2
    \$\begingroup\$ Welcome to Code Review! Nice question. \$\endgroup\$ – Heslacher Feb 28 at 6:33
10
\$\begingroup\$

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);
  }
|improve this answer|||||
\$\endgroup\$
  • 1
    \$\begingroup\$ Thanks for finding those bugs. And the refactor to AddIndexToLookup is beautifully concise, cheers! \$\endgroup\$ – MiniWalrus Feb 29 at 23:02
7
\$\begingroup\$
  • 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.

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ the same thoughts when I read the code. specially this, its extremely used which is uneeded, but in the other hand, I felt it's just a code habit ! which is understandable, but it gives the attention of an existing of another object with the same name. \$\endgroup\$ – iSR5 Feb 28 at 13:16
  • \$\begingroup\$ Thanks for the feedback @Heslacher! Definitely went overboard with the this keyword for this class, especially since the methods are mostly small. The reason I have this habit is at my workplace, code review is done via Azure DevOps, which shows pull request updates in a manner very similar to here at Code Review Stack Exchange. Our production code is not always concise, so having enforcing a this keyword in front of all members prevents any need for mind mapping class members to the current block of code being looked at. \$\endgroup\$ – MiniWalrus Feb 29 at 23:10
  • \$\begingroup\$ O and with regards to the protected members, I haven't given the full picture here (my bad!). Here is the repo containing the rest of the code. I wanted to test the internal array of the Heap class by overriding it with a test mock. \$\endgroup\$ – MiniWalrus Feb 29 at 23:14
7
\$\begingroup\$

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

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ This is especially good advice because because if one uses Floyd's heap construction it only takes O(n) for the initial elements. \$\endgroup\$ – Neil Feb 29 at 21:21
2
\$\begingroup\$

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.

|improve this answer|||||
\$\endgroup\$
2
\$\begingroup\$

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;
}
|improve this answer|||||
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.