Yet Another MinHeap

Clash Royale CLAN TAG#URR8PPP

up vote
4
down vote

favorite

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.

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="MinHeapT"/> that uses the default comparer.
 /// </summary>
 public MinHeap() : this(Comparer<T>.Default) 

 /// <summary>
 /// Creates an empty <see cref="MinHeapT"/> 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="MinHeapT"/> 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="MinHeapT"/> 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);
 
 

c# heap priority-queue

share|improve this question

edited 1 hour ago

asked 2 hours ago

Jason Watkins

1233

New contributor

Jason Watkins is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

• 
  
  
  

  
  

  
  
  
  
  
  

  
  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.
  – t3chb0t
  2 hours ago
  
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  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)
  – harold
  2 hours ago
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  @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.
  – Jason Watkins
  2 hours ago
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  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?
  – t3chb0t
  1 hour ago
  
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  @t3chb0t Fair point & done! :)
  – Jason Watkins
  1 hour ago
  

  
  
  
  

add a comment | 

up vote
4
down vote

favorite

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.

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="MinHeapT"/> that uses the default comparer.
 /// </summary>
 public MinHeap() : this(Comparer<T>.Default) 

 /// <summary>
 /// Creates an empty <see cref="MinHeapT"/> 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="MinHeapT"/> 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="MinHeapT"/> 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);
 
 

c# heap priority-queue

share|improve this question

edited 1 hour ago

asked 2 hours ago

Jason Watkins

1233

New contributor

Jason Watkins is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

• 
  
  
  

  
  

  
  
  
  
  
  

  
  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.
  – t3chb0t
  2 hours ago
  
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  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)
  – harold
  2 hours ago
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  @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.
  – Jason Watkins
  2 hours ago
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  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?
  – t3chb0t
  1 hour ago
  
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  @t3chb0t Fair point & done! :)
  – Jason Watkins
  1 hour ago
  

  
  
  
  

add a comment | 

up vote
4
down vote

favorite

up vote
4
down vote

favorite

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.

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="MinHeapT"/> that uses the default comparer.
 /// </summary>
 public MinHeap() : this(Comparer<T>.Default) 

 /// <summary>
 /// Creates an empty <see cref="MinHeapT"/> 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="MinHeapT"/> 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="MinHeapT"/> 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);
 
 

c# heap priority-queue

share|improve this question

edited 1 hour ago

asked 2 hours ago

Jason Watkins

1233

New contributor

Jason Watkins is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

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.

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="MinHeapT"/> that uses the default comparer.
 /// </summary>
 public MinHeap() : this(Comparer<T>.Default) 

 /// <summary>
 /// Creates an empty <see cref="MinHeapT"/> 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="MinHeapT"/> 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="MinHeapT"/> 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);
 
 

c# heap priority-queue

c# heap priority-queue

share|improve this question

edited 1 hour ago

asked 2 hours ago

Jason Watkins

1233

New contributor

Jason Watkins is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

share|improve this question

edited 1 hour ago

asked 2 hours ago

Jason Watkins

1233

New contributor

Jason Watkins is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

share|improve this question

share|improve this question

edited 1 hour ago

edited 1 hour ago

edited 1 hour ago

asked 2 hours ago

Jason Watkins

1233

New contributor

Jason Watkins is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

asked 2 hours ago

Jason Watkins

1233

asked 2 hours ago

Jason Watkins

1233

1233

New contributor

Jason Watkins is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

New contributor

Jason Watkins is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

Jason Watkins is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

• 
  
  
  

  
  

  
  
  
  
  
  

  
  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.
  – t3chb0t
  2 hours ago
  
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  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)
  – harold
  2 hours ago
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  @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.
  – Jason Watkins
  2 hours ago
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  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?
  – t3chb0t
  1 hour ago
  
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  @t3chb0t Fair point & done! :)
  – Jason Watkins
  1 hour ago
  

  
  
  
  

add a comment | 

• 
  
  
  

  
  

  
  
  
  
  
  

  
  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.
  – t3chb0t
  2 hours ago
  
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  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)
  – harold
  2 hours ago
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  @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.
  – Jason Watkins
  2 hours ago
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  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?
  – t3chb0t
  1 hour ago
  
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  @t3chb0t Fair point & done! :)
  – Jason Watkins
  1 hour ago
  

  
  
  
  

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.
– t3chb0t
2 hours ago

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.
– t3chb0t
2 hours ago

1

1

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)
– harold
2 hours ago

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)
– harold
2 hours ago

1

1

@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.
– Jason Watkins
2 hours ago

@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.
– Jason Watkins
2 hours ago

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?
– t3chb0t
1 hour ago

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?
– t3chb0t
1 hour ago

1

1

@t3chb0t Fair point & done! :)
– Jason Watkins
1 hour ago

@t3chb0t Fair point & done! :)
– Jason Watkins
1 hour ago

add a comment | 

1 Answer
1

active

oldest

votes

up vote
1
down vote

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 helper wrapping the comparinsons 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 like that, you'll be able to write a very nice looking conditions:

data[left] < data[largest]

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="MinHeapT"/> that uses the default comparer.
 /// </summary>
 public MinHeap() : this(Comparer<T>.Default) 

 /// <summary>
 /// Creates an empty <see cref="MinHeapT"/> 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="MinHeapT"/> 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="MinHeapT"/> 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]);
 

share|improve this answer

edited 8 mins ago

answered 18 mins ago

t3chb0t

32.9k744105

add a comment | 

Your Answer

StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
);
);
, "mathjax-editing");

StackExchange.ifUsing("editor", function ()
StackExchange.using("externalEditor", function ()
StackExchange.using("snippets", function ()
StackExchange.snippets.init();
);
);
, "code-snippets");

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "196"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);

Jason Watkins is a new contributor. Be nice, and check out our Code of Conduct.

 

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f206931%2fyet-another-minheap%23new-answer', 'question_page');

);

Post as a guest

Name Email

1 Answer
1

active

oldest

votes

1 Answer
1

active

oldest

votes

active

oldest

votes

active

oldest

votes

up vote
1
down vote

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 helper wrapping the comparinsons 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 like that, you'll be able to write a very nice looking conditions:

data[left] < data[largest]

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="MinHeapT"/> that uses the default comparer.
 /// </summary>
 public MinHeap() : this(Comparer<T>.Default) 

 /// <summary>
 /// Creates an empty <see cref="MinHeapT"/> 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="MinHeapT"/> 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="MinHeapT"/> 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]);
 

share|improve this answer

edited 8 mins ago

answered 18 mins ago

t3chb0t

32.9k744105

add a comment | 

up vote
1
down vote

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 helper wrapping the comparinsons 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 like that, you'll be able to write a very nice looking conditions:

data[left] < data[largest]

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="MinHeapT"/> that uses the default comparer.
 /// </summary>
 public MinHeap() : this(Comparer<T>.Default) 

 /// <summary>
 /// Creates an empty <see cref="MinHeapT"/> 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="MinHeapT"/> 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="MinHeapT"/> 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]);
 

share|improve this answer

edited 8 mins ago

answered 18 mins ago

t3chb0t

32.9k744105

add a comment | 

up vote
1
down vote

up vote
1
down vote

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 helper wrapping the comparinsons 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 like that, you'll be able to write a very nice looking conditions:

data[left] < data[largest]

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="MinHeapT"/> that uses the default comparer.
 /// </summary>
 public MinHeap() : this(Comparer<T>.Default) 

 /// <summary>
 /// Creates an empty <see cref="MinHeapT"/> 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="MinHeapT"/> 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="MinHeapT"/> 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]);
 

share|improve this answer

edited 8 mins ago

answered 18 mins ago

t3chb0t

32.9k744105

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 helper wrapping the comparinsons 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 like that, you'll be able to write a very nice looking conditions:

data[left] < data[largest]

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="MinHeapT"/> that uses the default comparer.
 /// </summary>
 public MinHeap() : this(Comparer<T>.Default) 

 /// <summary>
 /// Creates an empty <see cref="MinHeapT"/> 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="MinHeapT"/> 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="MinHeapT"/> 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]);
 

share|improve this answer

edited 8 mins ago

answered 18 mins ago

t3chb0t

32.9k744105

share|improve this answer

share|improve this answer

edited 8 mins ago

edited 8 mins ago

edited 8 mins ago

answered 18 mins ago

t3chb0t

32.9k744105

answered 18 mins ago

t3chb0t

32.9k744105

answered 18 mins ago

t3chb0t

32.9k744105

32.9k744105

add a comment | 

add a comment | 

Jason Watkins is a new contributor. Be nice, and check out our Code of Conduct.

 

draft saved

draft discarded

Jason Watkins is a new contributor. Be nice, and check out our Code of Conduct.

Jason Watkins is a new contributor. Be nice, and check out our Code of Conduct.

Jason Watkins is a new contributor. Be nice, and check out our Code of Conduct.

 

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f206931%2fyet-another-minheap%23new-answer', 'question_page');

);

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Name Email

Name

Email

Name Email

Name

Email