10
\$\begingroup\$

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);
        }
    }
}
\$\endgroup\$
  • \$\begingroup\$ Since I needed a MinHeap anyway - would you disclose your particular use for it? It would be tremendously useful to know where it can be applied in real-world rather than seeing yet-another-minheap ;-) Maybe you even have an example of such a use-case? This would be really great. \$\endgroup\$ – t3chb0t Nov 4 '18 at 17:58
  • 1
    \$\begingroup\$ I just did a kind of informal benchmark, as expected the minheap is a lot faster, about twice as fast for this load (adding 1K items, doing some random pushes and pops, then pop until empty) \$\endgroup\$ – harold Nov 4 '18 at 18:01
  • 1
    \$\begingroup\$ @t3chb0t I'm not sure the use cases for a priority queue are all that few and far between. 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. \$\endgroup\$ – Jason Watkins Nov 4 '18 at 18:18
  • \$\begingroup\$ Thanks! Yeah, I know, there might be quite a lot but they are not always easy to identify so this is exactly what I meant and it makes the question much more valuable to other readers too because they can see how to apply such things. Not just pure theory where you're wondering what do I do with that? ;-) Do you mind adding this comment to the question e.g. as a note? \$\endgroup\$ – t3chb0t Nov 4 '18 at 18:42
  • 2
    \$\begingroup\$ @t3chb0t Fair point & done! :) \$\endgroup\$ – Jason Watkins Nov 4 '18 at 19:01
4
\$\begingroup\$

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]);
    }
}
\$\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.