Skip to content

Instantly share code, notes, and snippets.

@coderodde coderodde/BinaryHeap.cs
Last active Jan 19, 2017

Embed
What would you like to do?
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;
}
}
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;
}
}
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;
}
}
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;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.