Created
October 18, 2017 23:07
-
-
Save bytefluxio/73e609fb7a81130900535b948b664609 to your computer and use it in GitHub Desktop.
Quick example implementation of a MinHeap
This file contains 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
| class MinHeap { | |
| private int Capacity { get; set; } | |
| private int Size { get; set; } | |
| private int[] Items; | |
| public MinHeap(int capacity) { | |
| Capacity = capacity; | |
| Size = 0; | |
| Items = new int[capacity]; | |
| } | |
| public MinHeap(int[] array) : this(array.Length) { | |
| foreach (var i in array) { | |
| Push(i); | |
| } | |
| } | |
| public int Peek() => Items[0]; | |
| public int Pop() { | |
| var ret = Items[0]; | |
| Items[0] = Items[--Size]; | |
| HeapifyDown(); | |
| return ret; | |
| } | |
| public int Pop(int quantity) { | |
| for (var i = 0; i < quantity-1; i++) Pop(); | |
| return Pop(); | |
| } | |
| public void Push(int item) { | |
| DoubleCapacityIfFull(); | |
| Items[Size++] = item; | |
| HeapifyUp(); | |
| } | |
| private void HeapifyUp() { | |
| var index = Size - 1; | |
| while (HasParent(index) && Parent(index) > Items[index]) { | |
| Swap(ParentIndex(index), index); | |
| index = ParentIndex(index); | |
| } | |
| } | |
| private void HeapifyDown() { | |
| var index = 0; | |
| while (HasLeftChild(index)) { | |
| int smallerChildIndex = LeftChildIndex(index); | |
| if (HasRightChild(index) && RightChild(index) < LeftChild(index)) { | |
| smallerChildIndex = RightChildIndex(index); | |
| } | |
| if (Items[index] < Items[smallerChildIndex]) break; | |
| else { | |
| Swap(index, smallerChildIndex); | |
| } | |
| index = smallerChildIndex; | |
| } | |
| } | |
| private int LeftChildIndex(int index) => 2 * index + 1; | |
| private int RightChildIndex(int index) => 2 * index + 2; | |
| private int ParentIndex(int index) => (index - 1) / 2; | |
| private bool HasLeftChild(int index) => LeftChildIndex(index) < Size; | |
| private bool HasRightChild(int index) => RightChildIndex(index) < Size; | |
| private bool HasParent(int index) => ParentIndex(index) >= 0; | |
| private int LeftChild(int index) => Items[LeftChildIndex(index)]; | |
| private int RightChild(int index) => Items[RightChildIndex(index)]; | |
| private int Parent(int index) => Items[ParentIndex(index)]; | |
| private void Swap(int indexA, int indexB) { | |
| int buffer = Items[indexA]; | |
| Items[indexA] = Items[indexB]; | |
| Items[indexB] = buffer; | |
| } | |
| private void DoubleCapacityIfFull() { | |
| if (Size != Capacity) return; | |
| var tmp = new int[Capacity*2]; | |
| for (var i = 0; i < Capacity; i++) { | |
| tmp[i] = Items[i]; | |
| } | |
| Capacity = Capacity*2; | |
| Items = tmp; | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment