Wsrtjtyk

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

        }

    }

}

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]);

    }

}