Skip to content

Instantly share code, notes, and snippets.

@WuchiOnline
Last active July 17, 2020 19:44
Show Gist options
  • Save WuchiOnline/02f3d23c166029d8beae78f6e04be757 to your computer and use it in GitHub Desktop.
Save WuchiOnline/02f3d23c166029d8beae78f6e04be757 to your computer and use it in GitHub Desktop.
C# MinHeap<T> where T: IComparable<T> Implementation
public class MinHeap<T> where T: System.IComparable<T>
{
public List<T> heapList {get; set;}
public int Count {get => heapList.Count;}
private int GetLeftChildIndex(int elementIndex) => 2 * elementIndex + 1;
private int GetRightChildIndex(int elementIndex) => 2 * elementIndex + 2;
private int GetParentIndex(int elementIndex) => (elementIndex - 1) / 2;
private bool HasLeftChild(int elementIndex) => GetLeftChildIndex(elementIndex) < Count;
private bool HasRightChild(int elementIndex) => GetRightChildIndex(elementIndex) < Count;
private bool IsRoot(int elementIndex) => elementIndex == 0;
private T GetLeftChild(int elementIndex) => heapList[GetLeftChildIndex(elementIndex)];
private T GetRightChild(int elementIndex) => heapList[GetRightChildIndex(elementIndex)];
private T GetParent(int elementIndex) => heapList[GetParentIndex(elementIndex)];
public MinHeap()
{
heapList = new List<T>();
}
public void PrintHeap()
{
foreach (T item in heapList)
{
Console.WriteLine(item.ToString());
}
}
public void Push (T item)
{
heapList.Add(item);
BubbleUp(Count - 1);
}
public T Pop ()
{
if (Count == 0)
{
throw new IndexOutOfRangeException();
}
// store copy to return at the end of the method
T firstItemCopy = heapList[0];
// move last item to first position
heapList[0] = heapList[Count - 1];
// remove the last thing off the list because it's redundant (it's now at the top of the heap)
heapList.RemoveAt(Count - 1);
FilterDown(0);
return firstItemCopy;
}
public T Peek()
{
if (Count == 0)
{
throw new IndexOutOfRangeException();
}
return heapList[0];
}
public bool IsEmpty()
{
return Count == 0;
}
void Swap (int firstIndex, int secondIndex)
{
T temp = heapList[firstIndex];
heapList[firstIndex] = heapList[secondIndex];
heapList[secondIndex] = temp;
}
void BubbleUp (int index)
{
while (!IsRoot(index) && heapList[index].CompareTo(GetParent(index)) < 0)
{
int parentIndex = GetParentIndex(index);
Swap(parentIndex, index);
index = parentIndex;
}
}
void FilterDown (int index)
{
// set currentIndex
int currentIndex = index;
// while loop: check if index has a left child
while (HasLeftChild(currentIndex))
{
// if it does, establish a smaller index
int smallerIndex = GetLeftChildIndex(currentIndex);
// check and see which of the left or right child has a smaller value
// allocate the smaller value child as the smaller index
if (HasRightChild(currentIndex) && GetRightChild(currentIndex).CompareTo(GetLeftChild(currentIndex)) < 0)
{
smallerIndex = GetRightChildIndex(currentIndex);
}
// if the element at smallerindex is bigger than the element at current index, then break
if (heapList[smallerIndex].CompareTo(heapList[currentIndex]) >= 0)
{
break;
}
// otherwise, swap element[currentindex] with element[smallerindex]
Swap(smallerIndex, currentIndex);
// set index to smallerIndex
currentIndex = smallerIndex;
// while loop will break when the index no longer has a left child
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment