Last active
July 17, 2020 19:44
-
-
Save WuchiOnline/02f3d23c166029d8beae78f6e04be757 to your computer and use it in GitHub Desktop.
C# MinHeap<T> where T: IComparable<T> Implementation
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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