BinaryHeap.cs

using System.Collections.Generic;
using System;

public sealed class BinaryHeap<T>
{
	private readonly List<T> _elements;

	private readonly Comparison<T> _compare;

	/// <summary>
	/// The amount of elements in the heap
	/// </summary>
	public int Count => _elements.Count;

	/// <summary>
	/// A read only list of elements
	/// </summary>
	public List<T> Elements => new List<T>(_elements);

	/// <summary>
	/// Returns the method that dictates how elements are compared
	/// </summary>
	public Comparison<T> Compare => _compare;

	/// <summary>
	/// Clears the heap of all elements
	/// </summary>
	public void Clear() { _elements.Clear(); }

	/// <summary>
	/// Initialises a new BinaryHeap with the specified compare function.
	/// </summary>
	/// <param name="compare">A method used to compare elements</param>
	public BinaryHeap(Comparison<T> compare)
	{
		_compare = compare;
		_elements = new List<T>();
	}

	/// <summary>
	/// Initialises a new BinaryHeap as a copy of the passed in heap
	/// </summary>
	/// <param name="heap">The heap to copy</param>
	public BinaryHeap(BinaryHeap<T> heap)
	{
		_elements = new List<T>(heap.Elements);
		_compare = heap.Compare;
	}

	/// <summary>
	/// Extracts the root
	/// </summary>
	/// <returns>The topmost object of the heap</returns>
	public T Extract()
	{
		if (_elements.Count == 0) throw new InvalidOperationException("The heap contains no elements");
		T node = _elements[0];

		if (_elements.Count <= 2)
			_elements.RemoveAt(0);
		else
		{
			_elements[0] = _elements[_elements.Count - 1];
			_elements.RemoveAt(_elements.Count - 1);
			BubbleDown(_elements[0]);
		}

		return node;
	}
	/// <summary>
	/// Inserts an element onto the heap
	/// </summary>
	/// <param name="entry">The object to add</param>
	public void Insert(T entry)
	{
		_elements.Add(entry);
		if ((_elements.Count - 1) == 0)
			return;

		BubbleUp(entry);

	}
	/// <summary>
	/// Peeks at the topmost object of the heap
	/// </summary>
	/// <returns>The top most object of the heap</returns>
	public T Peek()
	{
		//If a heap doesn't have any elements throw an exception
		if (_elements.Count == 0)
			throw new InvalidOperationException("The heap contains no elements");
		return _elements[0];
	}

	/// <summary>
	/// Should Element1 be swapped with Element2 based on our Compare Delegate
	/// </summary>
	/// <returns>true if it should, false if it should not</returns>
	private bool ShouldSwap(T element1, T element2)
	{
		var comparision = Compare(element1, element2);
		return comparision <= 0;
	}

	/// <summary>
	/// Swaps Element1 with Element2
	/// </summary>
	private void Swap(T element1, T element2)
	{
		//Swap the first element with the second
		int indexOfSecond = _elements.IndexOf(element2);
		_elements[_elements.IndexOf(element1)] = element2;
		_elements[indexOfSecond] = element1;


	}

	/// <summary>
	/// Bubbles the specified element down the heap until the heaps properties are restored
	/// </summary>
	/// <param name="element">The Element to bubble down</param>
	private void BubbleDown(T element)
	{
		int elementIndex = _elements.IndexOf(element), minElementIndex = 0;

		while (true)
		{
			int childLeftIndex = 2 * elementIndex + 1;

			//If the Child index exists outside the amount of elements in the heap then
			//the element is already at the bottom of the heap so we should break.
			if (childLeftIndex >= _elements.Count)
				break;

			element = _elements[elementIndex];
			var childElement = _elements[childLeftIndex];

			if (ShouldSwap(childElement, element))
				minElementIndex = childLeftIndex;

			int childRightIndex = childLeftIndex + 1;

			//If the right child exists it must be checked as well
			if (childRightIndex < _elements.Count)
			{

				element = _elements[minElementIndex];
				childElement = _elements[childRightIndex];

				if (ShouldSwap(childElement, element))
					minElementIndex = childRightIndex;
			}


			//If the minimum Element is still the original element of the loop
			//then the heap properties has been restored and we should break
			if (elementIndex == minElementIndex)
				break;

			//Since our element is out of order and violating the heaps properties it should be swapped
			Swap(_elements[elementIndex], _elements[minElementIndex]);


			elementIndex = minElementIndex;
		}

	}
	/// <summary>
	/// Bubbles an Element up the heap until the heaps properties are restored
	/// </summary>
	/// <param name="element">The element to bubble up</param>
	private void BubbleUp(T element)
	{
		int elementIndex = _elements.IndexOf(element);

		while (elementIndex > 0)
		{
			int parentIndex = (elementIndex - 1) / 2;

			T elementParent = _elements[parentIndex];
			if (ShouldSwap(element, elementParent))
			{
				Swap(element, elementParent);
				elementIndex = parentIndex;
			}
			else break;
		}

		_elements[elementIndex] = element;
	}
}

CoderoddeBinaryHeap.cs

using System.Collections.Generic;
using System;

public sealed class CoderoddeBinaryHeap<T>
{
	private readonly List<T> _elements;

	private readonly Comparison<T> _compare;

	/// <summary>
	/// The amount of elements in the heap
	/// </summary>
	public int Count => _elements.Count;

	/// <summary>
	/// A read only list of elements
	/// </summary>
	public List<T> Elements => new List<T>(_elements);

	/// <summary>
	/// Returns the method that dictates how elements are compared
	/// </summary>
	public Comparison<T> Compare => _compare;

	/// <summary>
	/// Clears the heap of all elements
	/// </summary>
	public void Clear() { _elements.Clear(); }

	/// <summary>
	/// Initialises a new BinaryHeap with the specified compare function.
	/// </summary>
	/// <param name="compare">A method used to compare elements</param>
	public CoderoddeBinaryHeap(Comparison<T> compare)
	{
		_compare = compare;
		_elements = new List<T>();
	}

	/// <summary>
	/// Initialises a new BinaryHeap as a copy of the passed in heap
	/// </summary>
	/// <param name="heap">The heap to copy</param>
	public CoderoddeBinaryHeap(BinaryHeap<T> heap)
	{
		_elements = new List<T>(heap.Elements);
		_compare = heap.Compare;
	}

	/// <summary>
	/// Extracts the root
	/// </summary>
	/// <returns>The topmost object of the heap</returns>
	public T Extract()
	{
		if (_elements.Count == 0) throw new InvalidOperationException("The heap contains no elements");
		T node = _elements[0];

		if (_elements.Count <= 2)
			_elements.RemoveAt(0);
		else
		{
			_elements[0] = _elements[_elements.Count - 1];
			_elements.RemoveAt(_elements.Count - 1);
			BubbleDown(0);
		}

		return node;
	}
	/// <summary>
	/// Inserts an element onto the heap
	/// </summary>
	/// <param name="entry">The object to add</param>
	public void Insert(T entry)
	{
		_elements.Add(entry);
		if ((_elements.Count - 1) == 0)
			return;
		
		BubbleUp(_elements.Count - 1);

	}
	/// <summary>
	/// Peeks at the topmost object of the heap
	/// </summary>
	/// <returns>The top most object of the heap</returns>
	public T Peek()
	{
		//If a heap doesn't have any elements throw an exception
		if (_elements.Count == 0)
			throw new InvalidOperationException("The heap contains no elements");
		return _elements[0];
	}

	/// <summary>
	/// Should Element1 be swapped with Element2 based on our Compare Delegate
	/// </summary>
	/// <returns>true if it should, false if it should not</returns>
	private bool ShouldSwap(T element1, T element2)
	{
		var comparision = Compare(element1, element2);
		return comparision <= 0;
	}

	/// <summary>
	/// Swaps Element1 with Element2
	/// </summary>
	private void Swap(T element1, T element2)
	{
		//Swap the first element with the second
		int indexOfSecond = _elements.IndexOf(element2);
		_elements[_elements.IndexOf(element1)] = element2;
		_elements[indexOfSecond] = element1;


	}

	/// <summary>
	/// Bubbles the specified element down the heap until the heaps properties are restored
	/// </summary>
	/// <param name="element">The Element to bubble down</param>
	private void BubbleDown(int index)
	{
		int leftChildIndex = GetLeftChildIndex(index);
		int rightChildIndex = leftChildIndex + 1;
		int topChildIndex = index;
		int count = _elements.Count;
		T targetElement = _elements[index];

		while (true)
		{
			if (leftChildIndex < count
				&& ShouldSwap(_elements[leftChildIndex],
							  targetElement))
			{
				topChildIndex = leftChildIndex;
			}

			if (topChildIndex == index)
			{
				if (rightChildIndex < count
					&& ShouldSwap(_elements[rightChildIndex],
								  targetElement))
				{
					topChildIndex = rightChildIndex;
				}
			}
			else if (rightChildIndex < count
					 && ShouldSwap(_elements[rightChildIndex],
								   _elements[leftChildIndex]))
			{
				topChildIndex = rightChildIndex;
			}

			if (topChildIndex == index)
			{
				_elements[topChildIndex] = targetElement;
				return;
			}

			_elements[index] = _elements[topChildIndex];

			index = topChildIndex;
			leftChildIndex = GetLeftChildIndex(index);
			rightChildIndex = leftChildIndex + 1;
		}
	}

	/// <summary>
	/// Bubbles an Element up the heap until the heaps properties are restored
	/// </summary>
	/// <param name="element">The element to bubble up</param>
	private void BubbleUp(int index)
	{
		if (index == 0)
		{
			return;
		}

		T targetNode = _elements[index];
		int parentNodeIndex = GetParentIndex(index);

		while (true)
		{
			if (ShouldSwap(targetNode, _elements[parentNodeIndex]))
			{
				_elements[index] = _elements[parentNodeIndex]; 
				index = parentNodeIndex;
				parentNodeIndex = GetParentIndex(index);
			}
			else
			{
				break;
			}

			if (index == 0)
			{
				break;
			}
		}

		_elements[index] = targetNode;
	}

	private int GetParentIndex(int childIndex)
	{
		return (childIndex - 1) >> 1;
	}

	private int GetLeftChildIndex(int index)
	{
		return (index << 1) + 1;
	}

	private int GetRightChildIndex(int index)
	{
		return (index + 1) << 1;
	}
}

Program.cs

using System;
using System.Linq;
using System.Collections.Generic;

class MainClass
{
	public static void Main(string[] args)
	{
		const int heapSize = 25 * 1000;

		int seed = (int) GetMilliseconds();
		var heapOp = new BinaryHeap<int>((m1, m2) => (m2.CompareTo(m1)));
		Random random = new Random(seed);
		long start = GetMilliseconds();
		for (int i = 0; i < heapSize; ++i)
		{
			heapOp.Insert(random.Next());
		}
		long end = GetMilliseconds();

		Console.WriteLine("Inserting into OP heap: {0} milliseconds.", end - start);


		var heapSlowCoderodde = new SlowerCoderoddeBinaryHeap<int>((m1, m2) => (m2.CompareTo(m1)));
		random = new Random(seed);
		start = GetMilliseconds();
		for (int i = 0; i < heapSize; ++i)
		{
			heapSlowCoderodde.Insert(random.Next());
		}
		end = GetMilliseconds();

		Console.WriteLine("Inserting into slower coderodde heap: {0} milliseconds.", end - start);

		var heapCoderodde = new CoderoddeBinaryHeap<int>((m1, m2) => (m2.CompareTo(m1)));
		random = new Random(seed);
		start = GetMilliseconds();
		for (int i = 0; i < heapSize; ++i)
		{
			heapCoderodde.Insert(random.Next());
		}
		end = GetMilliseconds();

		Console.WriteLine("Inserting into coderodde heap: {0} milliseconds.", end - start);

		List<int> opResultList = new List<int>();
		List<int> coderoddeResultList = new List<int>();
		List<int> slowCoderddeResultList = new List<int>();

		start = GetMilliseconds();
		while (heapOp.Count > 0)
		{
			opResultList.Add(heapOp.Extract());
		}
		end = GetMilliseconds();

		Console.WriteLine("Popped OP heap in {0} milliseconds.", end - start);

		start = GetMilliseconds();
		while (heapSlowCoderodde.Count > 0)
		{
			slowCoderddeResultList.Add(heapSlowCoderodde.Extract());
		}
		end = GetMilliseconds();

		Console.WriteLine("Popped slow coderodde heap in {0} milliseconds.", end - start);

		start = GetMilliseconds();
		while (heapCoderodde.Count > 0)
		{
			coderoddeResultList.Add(heapCoderodde.Extract());
		}
		end = GetMilliseconds();

		Console.WriteLine("Popped coderodde heap in {0} milliseconds.", end - start);
		Console.WriteLine("Heaps agree: {0}",
						  (opResultList.SequenceEqual(coderoddeResultList)
						   && opResultList.SequenceEqual(slowCoderddeResultList)));
	}

	private static long GetMilliseconds()
	{
		return DateTime.Now.Ticks / TimeSpan.TicksPerMillisecond;
	}
}

SlowerCoderoddeBinaryHeap.cs

using System.Collections.Generic;
using System;

public sealed class SlowerCoderoddeBinaryHeap<T>
{
	private readonly List<T> _elements;

	private readonly Comparison<T> _compare;

	/// <summary>
	/// The amount of elements in the heap
	/// </summary>
	public int Count => _elements.Count;

	/// <summary>
	/// A read only list of elements
	/// </summary>
	public List<T> Elements => new List<T>(_elements);

	/// <summary>
	/// Returns the method that dictates how elements are compared
	/// </summary>
	public Comparison<T> Compare => _compare;

	/// <summary>
	/// Clears the heap of all elements
	/// </summary>
	public void Clear() { _elements.Clear(); }

	/// <summary>
	/// Initialises a new BinaryHeap with the specified compare function.
	/// </summary>
	/// <param name="compare">A method used to compare elements</param>
	public SlowerCoderoddeBinaryHeap(Comparison<T> compare)
	{
		_compare = compare;
		_elements = new List<T>();
	}

	/// <summary>
	/// Initialises a new BinaryHeap as a copy of the passed in heap
	/// </summary>
	/// <param name="heap">The heap to copy</param>
	public SlowerCoderoddeBinaryHeap(BinaryHeap<T> heap)
	{
		_elements = new List<T>(heap.Elements);
		_compare = heap.Compare;
	}

	/// <summary>
	/// Extracts the root
	/// </summary>
	/// <returns>The topmost object of the heap</returns>
	public T Extract()
	{
		if (_elements.Count == 0) throw new InvalidOperationException("The heap contains no elements");
		T node = _elements[0];

		if (_elements.Count <= 2)
			_elements.RemoveAt(0);
		else
		{
			_elements[0] = _elements[_elements.Count - 1];
			_elements.RemoveAt(_elements.Count - 1);
			BubbleDown(0);
		}

		return node;
	}
	/// <summary>
	/// Inserts an element onto the heap
	/// </summary>
	/// <param name="entry">The object to add</param>
	public void Insert(T entry)
	{
		_elements.Add(entry);
		if ((_elements.Count - 1) == 0)
			return;

		BubbleUp(_elements.Count - 1);

	}
	/// <summary>
	/// Peeks at the topmost object of the heap
	/// </summary>
	/// <returns>The top most object of the heap</returns>
	public T Peek()
	{
		//If a heap doesn't have any elements throw an exception
		if (_elements.Count == 0)
			throw new InvalidOperationException("The heap contains no elements");
		return _elements[0];
	}

	/// <summary>
	/// Should Element1 be swapped with Element2 based on our Compare Delegate
	/// </summary>
	/// <returns>true if it should, false if it should not</returns>
	private bool ShouldSwap(T element1, T element2)
	{
		var comparision = Compare(element1, element2);
		return comparision <= 0;
	}

	private void Swap(int index1, int index2)
	{
		T tmp = _elements[index1];
		_elements[index1] = _elements[index2];
		_elements[index2] = tmp;
	}

	/// <summary>
	/// Bubbles the specified element down the heap until the heaps properties are restored
	/// </summary>
	/// <param name="element">The Element to bubble down</param>
	private void BubbleDown(int elementIndex)
	{
		T element = _elements[elementIndex];
		int minElementIndex = 0;

		while (true)
		{
			int childLeftIndex = 2 * elementIndex + 1;

			//If the Child index exists outside the amount of elements in the heap then
			//the element is already at the bottom of the heap so we should break.
			if (childLeftIndex >= _elements.Count)
				break;

			element = _elements[elementIndex];
			var childElement = _elements[childLeftIndex];

			if (ShouldSwap(childElement, element))
				minElementIndex = childLeftIndex;

			int childRightIndex = childLeftIndex + 1;

			//If the right child exists it must be checked as well
			if (childRightIndex < _elements.Count)
			{

				element = _elements[minElementIndex];
				childElement = _elements[childRightIndex];

				if (ShouldSwap(childElement, element))
					minElementIndex = childRightIndex;
			}


			//If the minimum Element is still the original element of the loop
			//then the heap properties has been restored and we should break
			if (elementIndex == minElementIndex)
				break;

			//Since our element is out of order and violating the heaps properties it should be swapped
			Swap(elementIndex, minElementIndex);
			elementIndex = minElementIndex;
		}

	}
	/// <summary>
	/// Bubbles an Element up the heap until the heaps properties are restored
	/// </summary>
	/// <param name="element">The element to bubble up</param>
	private void BubbleUp(int elementIndex)
	{
		T element = _elements[elementIndex];

		while (elementIndex > 0)
		{
			int parentIndex = (elementIndex - 1) / 2;

			T elementParent = _elements[parentIndex];
			if (ShouldSwap(element, elementParent))
			{
				Swap(elementIndex, parentIndex);
				elementIndex = parentIndex;
			}
			else break;
		}

		_elements[elementIndex] = element;
	}
}