Min&Max Heap implementation in .NET

Question

Overview

I was doing some performance optimization patterns when I stumbled upon PriorityQueue and I implemented for that reason Heap data structure, but I wanted you guys to tell me if I did something wrong. I am trying to achieve max performance and slight abstraction over the structure (what I mean by that is I gave the opportunity to the caller to decide if he creates max or min heap).

Code

IHeap.cs

namespace DataStructures.Heap
{
    using System.Collections.Generic;

    /// <summary>
    ///   Represents heap data structure.
    /// </summary>
    /// <typeparam name="T">Type of the parameters stored in the heap.</typeparam>
    public interface IHeap<T> : IEnumerable<T>
    {
        /// <summary>
        ///  Builds heap out of array.
        /// </summary>
        /// <param name="array">Array to build heap from.</param>
        void Build(T[] array);

        /// <summary>
        ///  Adds element to the heap.
        /// </summary>
        /// <param name="element">Element to add.</param>
        void Add(T element);

        /// <summary>
        ///  Extracts element from the heap.
        /// </summary>
        /// <returns> Extracted element.</returns>
        T Extract();
    }
}

HeapType.cs

namespace DataStructures.Heap
{
    /// <summary>
    ///  Used to describe what type a heap will be.
    /// </summary>
    public enum HeapType
    {
        /// <summary>
        ///  Max heap is a heap with largest element on top of each tree and sub-tree
        ///  when array is represented as a binary tree.
        /// </summary>
        Max,
        /// <summary>
        ///  Min heap is heap with smallest element on top of each tree and sub-tree
        ///  when array is represented as a binary tree.
        /// </summary>
        Min
    }
}

Heap.cs

namespace DataStructures.Heap
{
    using System;
    using System.Collections;
    using System.Collections.Generic;
    using System.Runtime.CompilerServices;

    /// <summary>
    ///  Represents max heap data struture.
    /// </summary>
    /// <typeparam name="T">Type of the elements in the heap.</typeparam>
    public class Heap<T> : IHeap<T>
    {
        private T[] _heap;
        private readonly HeapType _heapType;

        /// <summary>
        ///  Used to validate property of the heap. Either smallest 
        ///  element should be always root of each tree and sub-tree in a context of min heap
        ///  or largest when dealing with max heap.
        /// </summary>
        private readonly Func<int, int, T[], bool> _heapPropertyValidator;

        /// <summary>
        /// Initializes a new instance of the <see cref="Heap{T}"/> class.
        /// </summary>
        /// <param name="heap"> Array of type <typeparamref name="T"/></param>
        /// <param name="heapType"> Determines what kind of heap this instance will be. It can be any tye of <see cref="HeapType"/>.</param>
        public Heap(T[] heap, HeapType heapType)
        {
            _heap = heap;
            _heapType = heapType; 
            Count = heap.Length;

            switch (heapType)
            {
                case HeapType.Max:
                    _heapPropertyValidator =
                        (comparingIndex, comparingIndex2, array) =>
                            comparingIndex < Count && Comparer<T>.Default.Compare(array[comparingIndex], array[comparingIndex2]) > 0;
                    break;
                case HeapType.Min:
                    _heapPropertyValidator =
                        (comparingIndex, comparingIndex2, array) =>
                            comparingIndex < Count && Comparer<T>.Default.Compare(array[comparingIndex], array[comparingIndex2]) < 0;
                    break;
#if DEBUG
                default:
                    throw new ArgumentOutOfRangeException(nameof(heapType), heapType, null);
#endif
            }

            Build(_heap);
        }

        /// <summary>
        ///  Gets total number of elements in the heap.
        /// </summary>
        public int Count { get; private set; }
        public T this[int index]
        {
            get
            {
#if DEBUG
                if (index < 0)
                {
                    throw new ArgumentException(nameof(index));
                }
#endif
                return _heap[index];
            }
            set
            {
#if DEBUG
                if (value == null)
                {
                    throw new ArgumentNullException(nameof(value));
                }
#endif
                _heap[index] = value;
            }
        }

        /// <inheritdoc />
        /// <remarks> Takes O(nlogn) time complexity. </remarks>
        public void Add(T element)
        {
#if DEBUG
            if (element == null)
            {
                throw new ArgumentNullException(nameof(element));
            }
#endif
            _heap[Count] = element;
            Count++;

            Heapify(_heap, Count);
        }

        /// <remarks>
        ///  Maintains the heap property with the help of <see cref="_heapPropertyValidator"/> function.
        ///  Takes O(nlogn) time complexity. 
        /// </remarks>
        private void Heapify(T[] array, int index = 0)
        {
#if DEBUG
            if (array == null)
            {
                throw new ArgumentNullException(nameof(array));
            }
#endif
            while (true)
            {
                var left = Left(index);
                var right = Right(index);
                var toSwap = index;

                if(_heapPropertyValidator.Invoke(left, index, array))
                {
                    toSwap = left;
                }
                if(_heapPropertyValidator.Invoke(right, toSwap, array))
                {
                    toSwap = right;
                }
                if (toSwap != index)
                {
                    array.Swap(index, toSwap);
                    index = toSwap;
                    continue;
                }
                break;
            }
        }

        ///<inheritdoc />
        /// <remarks> Takes O(n) time complexity. </remarks>
        public void Build(T[] array)
        {
#if DEBUG
            if (array == null)
            {
                throw new ArgumentNullException(nameof(array));
            }
#endif
            for (var i = Count / 2; i >= 0; i--)
            {
                Heapify(array, i);
            }
        }

        /// <inheritdoc />
        /// <remarks> 
        ///  This method extracts top element of the heap. 
        ///  For max heap this is max element for min heap this is min element.
        ///  Time complexity of this method is O(logn).
        /// </remarks>
        public T Extract()
        {
            // first element is always max element.
            var result = _heap[0];

            // swap last element with first one and reduce the count, as we will
            // remove last element afterwards.
            _heap[0] = _heap[--Count];
            _heap = _heap.RemoveAt(Count);

            // heapify the heap as we broke the property.
            Heapify(_heap);
            return result;
        }

        /// <summary>
        ///  Sorts the heap without modifying it.
        /// </summary>
        /// <remarks> 
        ///  This method will sort the heap in asc(when the heap is of type min) and 
        ///  desc(when the heap is of type max). This has O(nlogn) time complexity.
        /// </remarks>
        /// <returns> Sorted enumerable in descending order.</returns>
        public IEnumerable<T> Sort()
        {
            // TODO: Check if move semantics are available in C#
            var heap = new Heap<T>(_heap, _heapType);
            var result = new T[Count];
            for (var i = 0; i < result.Length; i++)
            {
                result[i] = heap.Extract();
            }
            return result;
        }

        /// <summary>
        ///  Gets the parent index of the <paramref name="index"/>.
        /// </summary>
        /// <param name="index">Index to which parent index will be searched for.</param>
        /// <returns> Parent index. </returns>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        private static int Parent(int index)
            => (index & 1) == 0 ? (index >>= 1) - 1 : (index >>= 1);

        /// <summary>
        ///  Gets the index of left child of given index.
        /// </summary>
        /// <param name="index">Index to found left child index to.</param>
        /// <returns> Index of the left child of the element with given index.</returns>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        private static int Left(int index)
            => (index <<= 1) + 1;

        /// <summary>
        ///  Gets the index of right child of given index.
        /// </summary>
        /// <param name="index">Index to found right child index to.</param>
        /// <returns> Index of the right child of the element with given index.</returns>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        private static int Right(int index)
            => (index <<= 1) + 2;

        #region IEnumerable
        public IEnumerator<T> GetEnumerator() => ((IEnumerable<T>)_heap).GetEnumerator();
        IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
        #endregion
    }
}

Extensions.cs

using System;

namespace DataStructures
{
    public static class Extensions
    {
        /// <summary>
        ///  Swaps two elements at two given indexes.
        /// </summary>
        /// <typeparam name="T">Type of the elements in the array.</typeparam>
        /// <param name="array"> The array which will swap values from.</param>
        /// <param name="firstIndex"> Index that will be swaped with index number two.</param>
        /// <param name="secondIndex"> Index that will be swaped with index number one.</param>
        /// <throws><see cref="ArgumentException"/></throws>
        public static void Swap<T>(this T[] array, int firstIndex, int secondIndex)
        {
#if DEBUG
            if (array == null)
            {
               throw new ArgumentNullException(nameof(array));
            }
            if (firstIndex > array.Length || firstIndex < 0 ||
                secondIndex > array.Length || secondIndex < 0)
            {
                throw new ArgumentException("One of the indexes is out of range.");
            }
#endif
            var temp = array[firstIndex];
            array[firstIndex] = array[secondIndex];
            array[secondIndex] = temp;
        }

        /// <summary>
        ///  Removes element from array at index.
        /// </summary>
        /// <typeparam name="T">Type of the elements in the array.</typeparam>
        /// <param name="array"> Array to remove item from.</param>
        /// <param name="index"> Index which will be removed.</param>
        /// <returns>Returns new array without the element at passed index.</returns>
        public static T[] RemoveAt<T>(this T[] array, int index)
        {
#if DEBUG
            if (array == null)
            {
                throw new ArgumentNullException(nameof(array));
            }
            if (index < 0)
            {
                throw new ArgumentException(nameof(index));
            }
#endif
            var dest = new T[array.Length - 1];
            if (index > 0)
                Array.Copy(array, 0, dest, 0, index);

            if (index < array.Length - 1)
                Array.Copy(array, index + 1, dest, index, array.Length - index - 1);

            return dest;
        }
    }
}

Should I continue abstract the class by providing a way of passing heapPropertyValidator function or this should be concerns to the user of the heap?

Answer 1

Snowbody has already covered some of my pre-OP-edit answer... though I will disagree that HeapType has too many comments: inline documentation is great and should be as comprehensive as possible. There is a bit of overlap between our answers, but I think I've filtered out anything which doesn't add anything.

General Comments

Nice simple interface, though I'd personally appreciate properties for Count, Empty, and maybe a Peek() method. It is currently impossible to determine whether calling IHeap<T>.Extract() makes any sense, and it isn't clear what will happen if you do call Extract() on an empty Heap (I'll come back to that later...).

This comment on the Heap<T> class is misleading:

Represents max heap data struture.

Array and Build

Why is _heap an array?!?! The whole Build thing is a bit weird, but I can live with that. What I can't live with, is the fact that you are using a fixed-size array, not doing any upper-bounds checking on it, and not declaring that the Heap is limited by the size of the array it is built with! Don't use an array! Use a List<T>!!

Heap.ctor(T[], HeapType) modifies the provided array, and uses it for internal representation! This is a disaster of epic proportions! You've ruined the user's data, and now they can return the favour by corrupting your heap! Even more fun, because RemoveAt<T>(int) creates a new array (which is an \$O(n)\$ operation, and exactly something that Heaps are meant to avoid) this behaviour will change when Add is called. You should be using a List<T>, not an array, and you should be creating it yourself, not accepting it from in a constructor.

If you really want a fixed-size heap (as I think Snowbody is assuming, but if this is the case it should be clearly documented), then you just need to change RemoveAt(int) to default out the last element, rather than produce a new array.

The greatest sin, however, is that Build() - a public facing insance method - modifies the array it is passed and doesn't fill the Heap. This is exactly the opposite of the behaviour I would expect!

Member by Member stuff

_heapPropertyValidator

This feels really clunky. Why are you passing an array and two indicies, when you could just pass the two elements to be compared? Why is it a "Property Validator", when it could just be a comparer? Your 2 implementations in the constructor both perform a check on one of the elements, which should really be done by Heapify(T[], int) before calling it. It is completely unclear why this check is done.

I would use the existing Comparison delegate (or IComparer, as Snowbody says), and consider renaming it. This would allow you to provide a constructor which takes a custom comparator (because it wouldn't have any uncessary duties), but this wouldn't tally with it being either a min or max heap (unless you wrapped one explicitly and negated the comparison result, or modified Heapify).

You asked if this would be a good abstraction: given you don't need to remember the HeapType, I would say it would be valuable, not least because DefaultComparator is slow. However, you'd have to consider the API carefully, because currently it tries to be 'agnostic': if you accepted a comparator, you'd have to delare it as either a min or max heap in the appropriate constructors.

Heap.ctor(T[], HeapType)

#if DEBUG
    default:
        throw new ArgumentOutOfRangeException(nameof(heapType), heapType, null);
#endif

This is a valuable check: it shouldn't be restricted to debug mode.

You ought perhaps to be caching the result of Comparer<T>.Default: currently your lambdas have to look it up each time, and I can't remember if it does its own caching.

this[int]

I don't know why you have provided a public indexer: as far as I'm aware, no one has ever wanted to index into a Heap, it isn't terribly meaningful. You are sensibly checking whether the index is too small, but as Snowbody says, you also ought to be checking if it is too big (greater than or equal to Count), and you are only performing this check on the getter. As snowbody also says, the setter absolutely should not be public, because it can break the Heap. I would remove this indexer completely.

Personal choice, but I prefer the overloads of System.Diagnostics.Debug.Assert over #if DEBUG blocks. It isn't entirely clear why you would only want to run these checks under the debugger. A public method should be difficult (if it can't be impossible) to misuse without shouting at the consumer.

Add(T element)

Is there any particular reason why you disallow null values? This constraint should be documented.

You are assigning into an array at an index which may be greater than the array:

_heap[Count] = element;

As said before, _heap should be a dynamic structure controlled by the Heap: it should be perfectly fine to call Add on any Heap any time: the only allowable crash would be from tacitly ignored concurrancy concerns, or from lack of resources (Stack-overflow/Out-of-memory).

I havn't implemented a Heap myself for a while, but as Snowbody agrees, this looks very wrong:

Heapify(_heap, Count);

I think that Count shold be a 0. Count isn't even a valid index into _heap at this point. Quite simply, Add doesn't work; try this piece of code:

Heap<int> heap = new Heap<int>(new int[] { 5, 2, 6, 4, 1, 3 }, HeapType.Min);
Console.WriteLine(heap.Extract());
heap.Add(0);
Console.WriteLine(heap.Extract());

I took the liberty of re-writing RemoveAt so that it is constant-time, and doesn't reduce the size of the array, because otherwise this code would crash.

It should print 1 and then 0, but it prints 1 and then 2.

Takes O(nlogn) time complexity.

Should be O(log(n)).

Heapify

This is another confusing method which performs general operations on arrays, not on the data-structure.

Takes O(nlogn) time complexity.

Is hopefully a lie, it should be O(log(n)).

Build(T[])

Again, been a while since I had to understand Binary Heaps, so I couldn't say if this is right or not (cursory testing suggests it works), but it is not O(n), this is O(n*log(n)) it is O(n), my memory of algorithms betrays me again.

If this is to be a public facing method, then the null check should be kept for release builds.

Extract()

This method will crash if called on an Empty heap and throw an exception, which is good, but it will be a really unhelpful exception. You should be checking whether the Heap is empty, and throwing an IllegalOperation exception or similar with a meaningful message ("Can't extract an element from an empty heap").

You really need an IsEmpty or Count property on the interface, and perhaps a bool TryExtract(out T result) method so the Heap can be safely consumed.

RemoveAt is a problem. It makes this operation O(n), not O(log(n)), as it should be. It also replaces the array, which further confounds the whole escaped-state business. Use a List<T>, where calling RemoveAt(int) on the last element will be constant time (no copy).

Sort()

Without reading the comments, this looks like an in-place sort, which doesn't make much sense, but then nor does the comment, which suggests "this method will sort the heap". Consider rephrasing that to something along the lines of "this method will return every element in the Heap sorted...". I'd also consider renaming the method, to something like "EnumerateSorted()", but this is just taste.

You are missing an opportunity here to use yield to stream the sorted elements, which means if the consumer only needs half the elements, they can avoid poping the other half. This is kind of the behaviour I would expect from a Heap, otherwise there is no alogrithmic benefit to using a Heap rather than just enumerating the collection and using Quick/Merge/Genericnlogn Sort.

If you do wish to return a flat data-structure instead, then consider actually returning an array. I can't think of any real reason not to.

Time complexity looks correct on this one ;)

Parent(int)

I'm not sure what this is meant for... but it looks wrong, and it is never used, so remove it.

Key Points

• Do as Snowbody says, and encapsulate your own representation: don't expose this to anyone.

• Make that representation a List<T>, and call List<T>.Add(T) to add to it, and List<T>.RemoveAt(int) to remove from it.

• Add a Count member to the IHeap<T> interface

• Fix Add

• More comprehensive argument checks, and leave them in the release build

• TEST THE CODE

Answer 2

IHeap.cs

• Why are you inheriting from IEnumerable<T> ? I don't see any reason why your heap would need to support the IEnumerable methods.
• One typo: you put "parameter" instead of "element"
• might want to clarify that Extract() takes the highest-priority element off the heap.
• The interface is more for a priority queue than a heap. A heap is one way of implementing a priority queue. It also could be implemented by an ordered list, an unordered list, or a standard binary tree. I suggest changing the name to IPriorityQueue<T>.

HeapType.cs

• It's fine... probably has too many comments.
• I fully encourage you to allow the user to pass their own heapPropertyValidator delegate to the constructor. The type should be Func<T,T,bool>. Or maybe even IComparer<T>. The goal is to allow any item to be compared, even those that don't support >. (If you stick with this implementation of the class, you should probably make sure that T implements IComparable<T>.

Heap.cs

• It's a bad idea to expose the implementation of the class to users of the class. It's bad form to have the caller have to provide the storage! Your class should provide the storage. What if the caller change the array between calls to your code? Your code could produce wrong results. The class methods should be the only means of manipulating its state. The parameter should be the max heap size.
• public T this[int index] should throw IndexOutOfRangeException if the index is less than 0 or more than the current heap size.
• Why in the world are you allowing callers to modify arbitrary elements of the heap? That could break the heap property!
• public void Add(T element) should check if the heap is full, throwing an exception if it is. Also I'm pretty sure it's log n complexity, not n log n. (It can only bubble up through log n levels)
• Why does Heapify() take the array as a parameter? It's already a member variable/field!
• I believe Add() calls Heapify() with the wrong value for index, leading to bad results if (say) there are negative numbers. This is a bug. The spurious 0 elements might get brought up into the heap, while the negative numbers get lost. (It should use count/2 as does Build().)
• What's the possible benefit of the default argument index=0 on Heapify()?
• In Parent(), Left(), and Right(), you don't need to include the = sign in the shift operators; you're not needing to modify the value.