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