BinaryHeap.cs

usingSystem;
usingSystem.Collections.Generic;

namespaceDataStructures.Heap;

/// <summary>
/// A generic implementation of a binary heap.
/// </summary>
/// <remarks>
/// A binary heap is a complete binary tree that satisfies the heap property;
/// that is every node in the tree compares greater/less than or equal to its left and right
/// child nodes. Note that this is different from a binary search tree, where every node
/// must be the largest/smallest node of all of its children.
/// Although binary heaps are not very efficient, they are (probably) the simpliest heaps
/// to understand and implement.
/// More information: https://en.wikipedia.org/wiki/Binary_heap .
/// </remarks>
/// <typeparam name="T">Type of elements in binary heap.</typeparam>
publicclassBinaryHeap<T>
{
/// <summary>
/// Comparer to use when comparing elements.
/// </summary>
privatereadonlyComparer<T>comparer;

/// <summary>
/// List to hold the elements of the heap.
/// </summary>
privatereadonlyList<T>data;

/// <summary>
/// Initializes a new instance of the <see cref="BinaryHeap{T}" /> class.
/// </summary>
publicBinaryHeap()
{
data=newList<T>();
comparer=Comparer<T>.Default;
}

/// <summary>
/// Initializes a new instance of the <see cref="BinaryHeap{T}" /> class with a custom comparision function.
/// </summary>
/// <param name="customComparer">The custom comparing function to use to compare elements.</param>
publicBinaryHeap(Comparer<T>customComparer)
{
data=newList<T>();
comparer=customComparer;
}

/// <summary>
/// Gets the number of elements in the heap.
/// </summary>
publicintCount=>data.Count;

/// <summary>
/// Add an element to the binary heap.
/// </summary>
/// <remarks>
/// Adding to the heap is done by append the element to the end of the backing list,
/// and pushing the added element up until the heap property is restored.
/// </remarks>
/// <param name="element">The element to add to the heap.</param>
/// <exception cref="ArgumentException">Thrown if element is already in heap.</exception>
publicvoidPush(Telement)
{
data.Add(element);
HeapifyUp(data.Count-1);
}

/// <summary>
/// Remove the top/root of the binary heap (ie: the largest/smallest element).
/// </summary>
/// <remarks>
/// Removing from the heap is done by swapping the top/root with the last element in
/// the backing list, removing the last element, and pushing the new root down
/// until the heap property is restored.
/// </remarks>
/// <returns>The top/root of the heap.</returns>
/// <exception cref="InvalidOperationException">Thrown if heap is empty.</exception>
publicTPop()
{
if(Count==0)
{
thrownewInvalidOperationException("Heap is empty!");
}

varelem=data[0];
data[0]=data[^1];
data.RemoveAt(data.Count-1);
HeapifyDown(0);

returnelem;
}

/// <summary>
/// Return the top/root of the heap without removing it.
/// </summary>
/// <returns>The top/root of the heap.</returns>
/// <exception cref="InvalidOperationException">Thrown if heap is empty.</exception>
publicTPeek()
{
if(Count==0)
{
thrownewInvalidOperationException("Heap is empty!");
}

returndata[0];
}

/// <summary>
/// Returns element if it compares larger to the top/root of the heap, else
/// inserts element into the heap and returns the top/root of the heap.
/// </summary>
/// <param name="element">The element to check/insert.</param>
/// <returns>element if element compares larger than top/root of heap, top/root of heap otherwise.</returns>
publicTPushPop(Telement)
{
if(Count==0)
{
returnelement;
}

if(comparer.Compare(element,data[0])<0)
{
vartmp=data[0];
data[0]=element;
HeapifyDown(0);
returntmp;
}

returnelement;
}

/// <summary>
/// Check if element is in the heap.
/// </summary>
/// <param name="element">The element to check for.</param>
/// <returns>true if element is in the heap, false otherwise.</returns>
publicboolContains(Telement)=>data.Contains(element);

/// <summary>
/// Remove an element from the heap.
/// </summary>
/// <remarks>
/// In removing an element from anywhere in the heap, we only need to push down or up
/// the replacement value depending on how the removed value compares to its
/// replacement value.
/// </remarks>
/// <param name="element">The element to remove from the heap.</param>
/// <exception cref="ArgumentException">Thrown if element is not in heap.</exception>
publicvoidRemove(Telement)
{
varidx=data.IndexOf(element);

if(idx==-1)
{
thrownewArgumentException($"{element} not in heap!");
}

Swap(idx,data.Count-1);
vartmp=data[^1];
data.RemoveAt(data.Count-1);

if(idx<data.Count)
{
if(comparer.Compare(tmp,data[idx])>0)
{
HeapifyDown(idx);
}
else
{
HeapifyUp(idx);
}
}
}

/// <summary>
/// Swap the elements in the heap array at the given indices.
/// </summary>
/// <param name="idx1">First index.</param>
/// <param name="idx2">Second index.</param>
privatevoidSwap(intidx1,intidx2)
{
vartmp=data[idx1];
data[idx1]=data[idx2];
data[idx2]=tmp;
}

/// <summary>
/// Recursive function to restore heap properties.
/// </summary>
/// <remarks>
/// Restores heap property by swapping the element at <paramref name="elemIdx" />
/// with its parent if the element compares greater than its parent.
/// </remarks>
/// <param name="elemIdx">The element to check with its parent.</param>
privatevoidHeapifyUp(intelemIdx)
{
varparent=(elemIdx-1)/2;

if(parent>=0&&comparer.Compare(data[elemIdx],data[parent])>0)
{
Swap(elemIdx,parent);
HeapifyUp(parent);
}
}

/// <summary>
/// Recursive function to restore heap properties.
/// </summary>
/// <remarks>
/// Restores heap property by swapping the element at <paramref name="elemIdx" />
/// with the larger of its children.
/// </remarks>
/// <param name="elemIdx">The element to check with its children.</param>
privatevoidHeapifyDown(intelemIdx)
{
varleft=2*elemIdx+1;
varright=2*elemIdx+2;

varleftLargerThanElem=left<Count&&comparer.Compare(data[elemIdx],data[left])<0;
varrightLargerThanElem=right<Count&&comparer.Compare(data[elemIdx],data[right])<0;
varleftLargerThanRight=left<Count&&right<Count&&comparer.Compare(data[left],data[right])>0;

if(leftLargerThanElem&&leftLargerThanRight)
{
Swap(elemIdx,left);
HeapifyDown(left);
}
elseif(rightLargerThanElem&&!leftLargerThanRight)
{
Swap(elemIdx,right);
HeapifyDown(right);
}
}
}