Yet Another MinHeap

Question

So, this has been done quite a few times on here, but each of the linked implementations has some significant issues. Since I needed a MinHeap anyway, I figured I would throw my version into the ring.

In my case, I'm working on a toy game prototype where the simulation runs a clock that keeps track of the time in-game, and I have callbacks that I want to run at a particular game time, so the callbacks go into a priority queue and each time the simulation clock ticks up, I execute all of the callbacks that are before the new in-game time.

Previous Comments

First off, to address some comments on other implementations that I don't agree with:

If this is in production code you should consider using SortedSet

SortedSet<T> has a much more general API, and I'm not at all sure that it's as performant.

You should always try to program against an interface instead of against an implementation.

I agree for public APIs, but not for private implementation details. There's just no benefit whatsoever to using an interface for data.

Lingering Questions

One thing I'm undecided on is restricting T to be ICompareable<T>. While this sends a strong signal about the requirements of T when using the default comparer, it's unnecessarily restrictive in the case where the user wants to provide their own comparer.

I also wonder whether there is an implementation that is faster than an array-based binary heap. I've done a bit of poking around and tried implementing a pairing heap for comparison, and so far everything suggests that the array-based binary heap wins in practice for reasonable (say, less than 100k elements) heap sizes.

Code

Heap Implementation:

using System;
using System.Collections.Generic;

namespace CodeReview.DataStructures
{
    public sealed class MinHeap<T>
    {
        private readonly IComparer<T> comparer;
        private readonly List<T> data;

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

        /// <summary>
        /// Returns <see langword="true"/> if the heap is empty, otherwise
        /// <see langword="false"/>.
        /// </summary>
        public bool Empty => data.Count == 0;


        /// <summary>
        /// Creates an empty <see cref="MinHeap{T}"/> that uses the default comparer.
        /// </summary>
        public MinHeap() : this(Comparer<T>.Default) { }

        /// <summary>
        /// Creates an empty <see cref="MinHeap{T}"/> with the specified comparer.
        /// </summary>
        /// <param name="comparer">
        /// The comparer used to determine the order of elements in the heap.
        /// </param>
        /// <exception cref="ArgumentNullException">
        /// If <paramref name="comparer"/> is <see langword="null"/>.
        /// </exception>
        public MinHeap(IComparer<T> comparer)
        {
            this.comparer = comparer ?? throw new ArgumentNullException("comparer");
            data = new List<T>();
        }

        /// <summary>
        /// Creates a new <see cref="MinHeap{T}"/> containing the elements of
        /// <paramref name="src"/>.
        /// </summary>
        /// <param name="collection">
        /// The elements to add to the heap.
        /// </param>
        /// <exception cref="ArgumentNullException">
        /// If <paramref name="collection"/> is <see langword="null"/>.
        /// </exception>
        public MinHeap(IEnumerable<T> collection) : this(collection, Comparer<T>.Default) { }

        /// <summary>
        /// Creates a new <see cref="MinHeap{T}"/> containing the elements of
        /// <paramref name="collection"/>.
        /// </summary>
        /// <param name="collection">
        /// The elements to add to the heap.
        /// </param>
        /// <param name="comparer">
        /// The comparer used to determine the order of elements in the heap.
        /// </param>
        /// <exception cref="ArgumentNullException">
        /// If <paramref name="collection"/> or <paramref name="comparer"/> are
        /// <see langword="null"/>.
        /// </exception>
        public MinHeap(IEnumerable<T> collection, IComparer<T> comparer)
        {
            this.comparer = comparer ?? throw new ArgumentNullException("comparer");
            data = new List<T>(collection);
            for (int i = Count / 2; i >= 0; --i)
            {
                SiftDown(i);
            }
        }

        /// <summary>
        /// Gets the item at the top of the heap.
        /// </summary>
        /// <returns>The item at the top of the heap.</returns>
        /// <exception cref="InvalidOperationException">
        /// If the heap is empty.
        /// </exception>
        public T Peek()
        {
            if (Empty)
            {
                throw new InvalidOperationException("Cannot peek empty heap");
            }
            return data[0];
        }

        /// <summary>
        /// Removes the item at the top of the heap and returns it.
        /// </summary>
        /// <returns>The item at the top of the heap.</returns>
        /// <exception cref="InvalidOperationException">
        /// If the heap is empty.
        /// </exception>
        public T Pop()
        {
            if (Empty)
            {
                throw new InvalidOperationException("Cannot pop empty heap");
            }
            T result = data[0];
            data[0] = data[Count - 1];
            data.RemoveAt(Count - 1);
            SiftDown(0);
            return result;
        }

        /// <summary>
        /// Inserts the specified item into the heap.
        /// </summary>
        /// <param name="item">The item to insert.</param>
        public void Push(T item)
        {
            data.Add(item);
            SiftUp(Count - 1);
        }

        /// <summary>
        /// Replaces the item at the top of the heap with <paramref name="item"/>
        /// and returns the old top.
        /// </summary>
        /// <param name="item">The item to insert.</param>
        /// <returns>The previous top of the heap.</returns>
        /// <exception cref="InvalidOperationException">
        /// If the heap is empty.
        /// </exception>
        /// <remarks>
        /// This operation is useful because it only needs to rebalance the heap
        /// once, as opposed to two rebalances for a pop followed by a push.
        /// </remarks>
        public T Replace(T item)
        {
            if (Empty)
            {
                throw new InvalidOperationException("Cannot replace on empty heap");
            }
            T result = data[0];
            data[0] = item;
            SiftDown(0);
            return result;
        }

        private void SiftUp(int index)
        {
            while (index > 0)
            {
                int parent = (index - 1) / 2;
                if (comparer.Compare(data[index], data[parent]) < 0)
                {
                    Swap(index, parent);
                    index = parent;
                }
                else
                {
                    return;
                }
            }
        }

        private void SiftDown(int i)
        {
            while (i < Count)
            {
                int left = 2 * i + 1;
                int right = 2 * i + 2;
                int largest = i;
                if (left < Count && comparer.Compare(data[left], data[largest]) < 0)
                {
                    largest = left;
                }
                if (right < Count && comparer.Compare(data[right], data[largest]) < 0)
                {
                    largest = right;
                }


                if (largest == i)
                {
                    return;
                }
                Swap(i, largest);

                i = largest;
            }
        }

        private void Swap(int i, int j)
        {
            T tmp = data[j];
            data[j] = data[i];
            data[i] = tmp;
        }
    }
}

Unit Tests:

using System;
using System.Collections.Generic;

using Microsoft.VisualStudio.TestTools.UnitTesting;

using CodeReview.DataStructures;

namespace CodeReview.Test.DataStructures
{
    [TestClass]
    public class MinHeapTests
    {
        [TestMethod]
        public void Count()
        {
            var heap = new MinHeap<int>();
            Assert.AreEqual(0, heap.Count);

            heap.Push(10);
            Assert.AreEqual(1, heap.Count);

            heap.Push(1);
            Assert.AreEqual(2, heap.Count);

            heap.Push(20);
            Assert.AreEqual(3, heap.Count);

            heap.Pop();
            Assert.AreEqual(2, heap.Count);

            heap.Pop();
            Assert.AreEqual(1, heap.Count);

            heap.Pop();
            Assert.AreEqual(0, heap.Count);
        }

        [TestMethod]
        public void Empty()
        {
            var heap = new MinHeap<int>();
            Assert.AreEqual(0, heap.Count);
            Assert.IsTrue(heap.Empty);

            heap.Push(10);
            Assert.IsFalse(heap.Empty);

            heap.Push(5);
            Assert.IsFalse(heap.Empty);

            heap.Pop();
            Assert.IsFalse(heap.Empty);

            heap.Pop();
            Assert.IsTrue(heap.Empty);
        }

        [TestMethod]
        public void PushPeek1()
        {
            var heap = new MinHeap<int>();

            heap.Push(10);
            Assert.AreEqual(10, heap.Peek());
        }

        [TestMethod]
        public void PushPeek2()
        {
            var heap = new MinHeap<int>();

            heap.Push(10);
            heap.Push(5);
            Assert.AreEqual(5, heap.Peek());
        }

        [TestMethod]
        public void PushPeek3()
        {
            var heap = new MinHeap<int>();

            heap.Push(10);
            heap.Push(5);
            heap.Push(20);
            Assert.AreEqual(5, heap.Peek());
        }

        [TestMethod]
        public void PushPeekRandom()
        {
            const int COUNT = 200;
            var heap = new MinHeap<int>();
            var rng = new Random();
            var elements = new List<int>(COUNT);

            int min = Int32.MaxValue;
            for (int i = 0; i < COUNT; ++i)
            {
                int value = rng.Next();
                if (value < min)
                {
                    min = value;
                }

                heap.Push(value);
                Assert.AreEqual(min, heap.Peek());
            }
        }

        [TestMethod]
        public void PushPop1()
        {
            var heap = new MinHeap<int>();

            heap.Push(10);
            Assert.AreEqual(10, heap.Pop());
        }

        [TestMethod]
        public void PushPop2()
        {
            var heap = new MinHeap<int>();

            heap.Push(10);
            heap.Push(5);
            Assert.AreEqual(5, heap.Pop());
            Assert.AreEqual(10, heap.Pop());
        }

        [TestMethod]
        public void PushPop3()
        {
            var heap = new MinHeap<int>();

            heap.Push(10);
            heap.Push(5);
            heap.Push(20);
            Assert.AreEqual(5, heap.Pop());
            Assert.AreEqual(10, heap.Pop());
            Assert.AreEqual(20, heap.Pop());
        }

        [TestMethod]
        public void PushPopRandom()
        {
            const int COUNT = 200;
            var heap = new MinHeap<int>();
            var rng = new Random();
            var elements = new List<int>(COUNT);
            for (int i = 0; i < COUNT; ++i)
            {
                int value = rng.Next();
                elements.Add(value);
                heap.Push(value);
            }

            elements.Sort();
            for (int i = 0; i < COUNT; ++i)
            {
                Assert.AreEqual(elements[i], heap.Pop());
            }
        }

        [TestMethod]
        public void ReplacePeek1()
        {
            var heap = new MinHeap<int>();

            heap.Push(2);
            int result = heap.Replace(1);
            Assert.AreEqual(2, result);
            Assert.AreEqual(1, heap.Peek());
        }

        [TestMethod]
        public void ReplacePeek2()
        {
            var heap = new MinHeap<int>();

            heap.Push(20);
            heap.Push(10);
            int result = heap.Replace(30);
            Assert.AreEqual(10, result);
            Assert.AreEqual(20, heap.Peek());
        }

        [TestMethod]
        [ExpectedException(typeof(InvalidOperationException))]
        public void PeekEmpty()
        {
            var heap = new MinHeap<int>();
            heap.Peek();
        }

        [TestMethod]
        [ExpectedException(typeof(InvalidOperationException))]
        public void PopEmpty()
        {
            var heap = new MinHeap<int>();
            heap.Pop();
        }

        [TestMethod]
        [ExpectedException(typeof(InvalidOperationException))]
        public void ReplaceEmpty()
        {
            var heap = new MinHeap<int>();
            int item = heap.Replace(0);
        }


        [TestMethod]
        public void ConstructFromArray2()
        {
            int[] elements = new int[] { 10, 20 };
            var heap = new MinHeap<int>(elements);

            Assert.AreEqual(2, heap.Count);
            Assert.AreEqual(10, heap.Peek());
        }


        [TestMethod]
        public void ConstructFromArrayRandom()
        {
            const int COUNT = 200;
            var rng = new Random();
            var elements = new int[COUNT];
            for (int i = 0; i < COUNT; ++i)
            {
                elements[i] = rng.Next();
            }
            var heap = new MinHeap<int>(elements);

            Array.Sort(elements);
            for (int i = 0; i < COUNT; ++i)
            {
                Assert.AreEqual(elements[i], heap.Pop());
            }
        }


        [TestMethod]
        [ExpectedException(typeof(ArgumentNullException))]
        public void ConstructFromNullEnumerable()
        {
            var heap = new MinHeap<int>((IEnumerable<int>)null);
        }


        [TestMethod]
        [ExpectedException(typeof(ArgumentNullException))]
        public void ConstructFromNullComparer()
        {
            var heap = new MinHeap<int>((IComparer<int>)null);
        }


        [TestMethod]
        [ExpectedException(typeof(ArgumentNullException))]
        public void ConstructFromArrayAndNullComparer()
        {
            var heap = new MinHeap<int>(new int[0], (IComparer<int>)null);
        }
    }
}

Answer 1

This is a very nice and clean implementation and looks like there's not much to complain about but I have a few thoughts.

---

One thing I'm undecided on is restricting T to be ICompareable<T>. While this sends a strong signal about the requirements of T when using the default comparer, it's unnecessarily restrictive in the case where the user wants to provide their own comparer.

I wouldn't say this is unnecessarily restrictive and in the .NET world this is an established way for such things. I as a seasoned C# user woulnd't expect anything else there but exactly this interface for providing my own logic. This feels the most natural thing to do to me - and very likely to others too. I even have small utility for creating them. (You can look for ComparerFactory here.)

---

Some tiny nitpicks...

• The Empty property should be called IsEmpty as the former one is not precise enough and suggests returning an empty MinHeap<T> rather then being a flag.

• You can simplify the Swap operation with tuples:

  private void Swap(int i, int j)
  {
      (data[j], data[i]) = (data[i], data[j]);        
  }
  

---

With the comparer you could go insane and add a decorator wrapping the comparisons and translating them to more friednly operators < and >

internal class Comparable<T> : IComparable<T>
{
    private readonly T _value;
    private readonly IComparer<T> _comparer;

    public Comparable(T value, IComparer<T> comparer)
    {
        _value = value;
        _comparer = comparer;
    }

    public int CompareTo(T other) => _comparer.Compare(_value, other);

    public static implicit operator T(Comparable<T> comparable) => comparable._value;

    public static bool operator <(Comparable<T> left, Comparable<T> right) => left.CompareTo(right._value) < 0;

    public static bool operator >(Comparable<T> left, Comparable<T> right) => left.CompareTo(right._value) > 0;
}

When you then replace the T with it for List<Comparable<T>> data, you'll be able to write a very nice looking conditions:

comparer.Compare(data[left], data[largest]) < 0

will become:

 data[left] < data[largest]

and the implicit cast will allow you to return the value without additional effort so here nothing changes:

  public T Peek()
  {
      if (Empty)
      {
          throw new InvalidOperationException("Cannot peek empty heap");
      }
      return data[0];
  }

Example: (I'm not sure I didn't broke anything, I haven't run the tests)

public sealed class MinHeap<T>
{
    private readonly IComparer<T> comparer;
    private readonly List<Comparable<T>> data;

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

    /// <summary>
    /// Returns <see langword="true"/> if the heap is empty, otherwise
    /// <see langword="false"/>.
    /// </summary>
    public bool Empty => data.Count == 0;


    /// <summary>
    /// Creates an empty <see cref="MinHeap{T}"/> that uses the default comparer.
    /// </summary>
    public MinHeap() : this(Comparer<T>.Default) { }

    /// <summary>
    /// Creates an empty <see cref="MinHeap{T}"/> with the specified comparer.
    /// </summary>
    /// <param name="comparer">
    /// The comparer used to determine the order of elements in the heap.
    /// </param>
    /// <exception cref="ArgumentNullException">
    /// If <paramref name="comparer"/> is <see langword="null"/>.
    /// </exception>
    public MinHeap(IComparer<T> comparer)
    {
        this.comparer = comparer ?? throw new ArgumentNullException("comparer");
        data = new List<Comparable<T>>();
    }

    /// <summary>
    /// Creates a new <see cref="MinHeap{T}"/> containing the elements of
    /// <paramref name="src"/>.
    /// </summary>
    /// <param name="collection">
    /// The elements to add to the heap.
    /// </param>
    /// <exception cref="ArgumentNullException">
    /// If <paramref name="collection"/> is <see langword="null"/>.
    /// </exception>
    public MinHeap(IEnumerable<T> collection) : this(collection, Comparer<T>.Default) { }

    /// <summary>
    /// Creates a new <see cref="MinHeap{T}"/> containing the elements of
    /// <paramref name="collection"/>.
    /// </summary>
    /// <param name="collection">
    /// The elements to add to the heap.
    /// </param>
    /// <param name="comparer">
    /// The comparer used to determine the order of elements in the heap.
    /// </param>
    /// <exception cref="ArgumentNullException">
    /// If <paramref name="collection"/> or <paramref name="comparer"/> are
    /// <see langword="null"/>.
    /// </exception>
    public MinHeap(IEnumerable<T> collection, IComparer<T> comparer)
    {
        this.comparer = comparer ?? throw new ArgumentNullException("comparer");
        data = new List<Comparable<T>>(collection.Select(c => new Comparable<T>(c, comparer)));
        for (int i = Count / 2; i >= 0; --i)
        {
            SiftDown(i);
        }
    }

    /// <summary>
    /// Gets the item at the top of the heap.
    /// </summary>
    /// <returns>The item at the top of the heap.</returns>
    /// <exception cref="InvalidOperationException">
    /// If the heap is empty.
    /// </exception>
    public T Peek()
    {
        if (Empty)
        {
            throw new InvalidOperationException("Cannot peek empty heap");
        }
        return data[0];
    }

    /// <summary>
    /// Removes the item at the top of the heap and returns it.
    /// </summary>
    /// <returns>The item at the top of the heap.</returns>
    /// <exception cref="InvalidOperationException">
    /// If the heap is empty.
    /// </exception>
    public T Pop()
    {
        if (Empty)
        {
            throw new InvalidOperationException("Cannot pop empty heap");
        }
        T result = data[0];
        data[0] = data[Count - 1];
        data.RemoveAt(Count - 1);
        SiftDown(0);
        return result;
    }

    /// <summary>
    /// Inserts the specified item into the heap.
    /// </summary>
    /// <param name="item">The item to insert.</param>
    public void Push(T item)
    {
        data.Add(new Comparable<T>(item, comparer));
        SiftUp(Count - 1);
    }

    /// <summary>
    /// Replaces the item at the top of the heap with <paramref name="item"/>
    /// and returns the old top.
    /// </summary>
    /// <param name="item">The item to insert.</param>
    /// <returns>The previous top of the heap.</returns>
    /// <exception cref="InvalidOperationException">
    /// If the heap is empty.
    /// </exception>
    /// <remarks>
    /// This operation is useful because it only needs to rebalance the heap
    /// once, as opposed to two rebalances for a pop followed by a push.
    /// </remarks>
    public T Replace(T item)
    {
        if (Empty)
        {
            throw new InvalidOperationException("Cannot replace on empty heap");
        }
        T result = data[0];
        data[0] = new Comparable<T>(item, comparer);
        SiftDown(0);
        return result;
    }

    private void SiftUp(int index)
    {
        while (index > 0)
        {
            int parent = (index - 1) / 2;
            if (comparer.Compare(data[index], data[parent]) < 0)
            {
                Swap(index, parent);
                index = parent;
            }
            else
            {
                return;
            }
        }
    }

    private void SiftDown(int i)
    {
        while (i < Count)
        {
            int left = 2 * i + 1;
            int right = 2 * i + 2;
            int largest = i;
            if (left < Count && data[left] < data[largest])
            {
                largest = left;
            }
            if (right < Count && data[right] < data[largest])
            {
                largest = right;
            }


            if (largest == i)
            {
                return;
            }
            Swap(i, largest);

            i = largest;
        }
    }

    private void Swap(int i, int j)
    {
        (data[j], data[i]) = (data[i], data[j]);
    }
}