Create a C# Program that has Binary Heap operation: AddItem, deleteRoot , MoveDown, MoveUP and Heapsort.

----- code is provded below------ please include testings

class BinaryHeap : IEnumerable where T : IComparable { private T[] array; private int currentIndex = -1; public BinaryHeap(int size) { array = new T[size]; currentIndex = 0; } public T GetItem(int index) { return array[index]; } private void SetItem(int index, T value) { if (index >= array.Length) Grow(array.Length * 2); array[index] = value; } private void Grow(int newsize) { Array.Resize(ref array, newsize); }

private int LeftChild(int pos) { return 2 * pos + 1; } private int RightChild(int pos) { return 2 * pos + 2; } public IEnumerator GetEnumerator() { for (int index = 0; index < array.Length; index++) { // Yield each element yield return array[index]; } }

public void HeapSort() { // Implement This // }

public void AddItem(T value) { // you need to make this code actually insert in a tree like fashion, not just this SetItem(currentIndex, value); currentIndex++; //heapifyUp(); //Insert Logic // If the tree is empty, insert at the bottom (it does that already) // if not, insert at the end, // From the end you either need to swap to the root, and keep minheapify // or, you should probably implement move up // for that you run a while loop, check if the current position both isn't the root, and is higher priority than a parent (in this case that probably means it's a lower value) // if it is, swap with parent, and keep doing that until it's its in the } public void MoveUp(int position) { // given an array index, it should keep moving it up the array until it gets to the right spot }

//ExtractRoot (which is the same as extract min in our case) public T ExtractHead() { // check to make sure the heap isn't empty, if it is, return a 'null' or at least, default object if (currentIndex <= 0) // change to count in assignment if you use that return default(T); // this should get the head T head = array[0]; //then in the lab you need to implement this part yourself //array[0] needs to get some value (most likely it will be array[0] = array[Count-1] // then remove the data at [count-1], and make sure you don't try and use that data later (remember you can do array[x] = default(T)) //then Minheapify the array

return head; } // public void Swap(int position1, int position2) { T first = array[position1]; array[position1] = array[position2]; array[position2] = first; } //heapify should heapify the subtree for the element i that is the root of a subtree public void MoveDown(int position) { int root = position; // while the root has at least one child while ((2 * root + 1) <= currentIndex) { // root*2+1 points to the left child int child = 2 * root + 1; // take the highest of the left or right child if ((child + 1) <= currentIndex && (array[child].CompareTo(array[child + 1])) < 0) { // then point to the right child instead child = child + 1; }

// out of max-heap order // swap the child with root if child is greater if ((array[root].CompareTo(array[child])) < 0) { T tmp = array[root]; array[root] = array[child]; array[child] = tmp;

// return the swapped root to test against // it's new children root = child; } else { return; } } }

public void buildMaxHeap() { int midPoint = array.Length / 2; for (int indexsOfLeaves = midPoint; indexsOfLeaves >= 0; indexsOfLeaves--) { MinHeapify(indexsOfLeaves); } }

//MinHeapify Should be complete but it might have bugs (sorry, these things are hard to test) public void MinHeapify(int position) { int lchild = LeftChild(position); int rchild = RightChild(position); int largest = 0; // unused int smallest = position; //I'm not 100% sure these if statements are right (sorry)

if (currentIndex > lchild && (array[lchild].CompareTo(array[position])) < 0) //note that I'm using currentIndex as the heap size which is a bad naming convention { smallest = lchild; }

if (currentIndex > rchild && (array[rchild].CompareTo(array[position])) < 0) //note that I'm using currentIndex as the heap size which is a bad naming convention { smallest = rchild; } if (smallest != position) { Swap(position, smallest); MinHeapify(smallest); }

}

//public void heapifyUp(){ // int index = sizeof -1; // while(HashSetParent(index)&& parent(index)> items[index]){Swap(getParentIndex(index), index); // index = getParentIndex(index); // }}

//public void heapifyDown(){ // int index = 0; // while(hasLeftChild(index)){ // int smallerChildIndex = getLeftChildIndex(index); // if (hasRightChild(index) && RightChild(index) < LeftChild(index)) { smallerChildIndex = getRightChildIndex(index); } // if (items[index] < items[smallerChildIndex]) // { // break; // } // else // { // Swap(index, smallerChildIndex); // } // index = smallerChildIndex; // }} // }}

} }