Last active
August 19, 2020 21:46
-
-
Save WuchiOnline/7e2a0f7d2834a5036481d1d5da705ffa to your computer and use it in GitHub Desktop.
C# MaxHeap<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 MaxHeap<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 MaxHeap() | |
{ | |
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 bigger index | |
int biggerIndex = GetLeftChildIndex(currentIndex); | |
// check and see which of the left or right child has a bigger value | |
// allocate the bigger value child as the bigger index | |
if (HasRightChild(currentIndex) && GetRightChild(currentIndex).CompareTo(GetLeftChild(currentIndex)) > 0) | |
{ | |
biggerIndex = GetRightChildIndex(currentIndex); | |
} | |
// if the element at biggerIndex is smaller than the element at currentIndex, then break | |
if (heapList[biggerIndex].CompareTo(heapList[currentIndex]) <= 0) | |
{ | |
break; | |
} | |
// otherwise, swap element[currentIndex] with element[biggerIndex] | |
Swap(biggerIndex, currentIndex); | |
// set index to biggerIndex | |
currentIndex = biggerIndex; | |
// 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