Your task: Implement a MinHeap. In the MyMinHeap.java file, add the following:

Instance variables:

Instance Variable	Description
protected ArrayList data	The underlying data structure of MyMinHeap. You must use 0-based indexing to store the heap (the root of the tree at index 0).

In this file, you may import the following:

java.util.ArrayList

java.util.Collection

MyMinHeap should have a constraint on the generic parameter E such that E implements Comparable so you can compare the elements. You should also implement MyMinHeapInterface.

Note: Do not add any other instance variables and do not add any static variables (other than private static final variables to be used as constants).

Constructors:

Constructor	Description
public MyMinHeap()	No-argument constructor that initializes data to an empty ArrayList.
public MyMinHeap(Collection collection)	Initializes a min-heap using the elements in collection. First, initialize data using the ArrayList(Collection collection) constructor by directly passing in the collection argument. Next, iterate through data backward, percolating each element down. We will soon write the percolateDown() helper method, which can be used here. Throws NullPointerException if collection or any element in collection is null.

Helper Methods:

You should find these methods useful to implement the actual functionality of MyMinHeap and also to implement other helper methods.

Important Note: These helper methods are meant to be called inside the core methods and other helper methods. Therefore, you have some design choice in the helper methods for 1) whether you want to assume all arguments are in-bounds and 2) if you do not want to assume, then what out-of-bounds behavior you want. If you assume all arguments are in bounds, you must make sure that all arguments follow the assumptions before calling your helper method.

Note:

In practice, these would be private methods, but for our assignment, they will be protected so that we can auto-grade your methods and provide feedback for them. To be clear, these methods are required.

All tests assume that you use 0-based indexing to store the heap in the array.

Helper Method Name	Description
protected void swap(int from, int to)	Swap the elements at from and to indices in data. You may assume from and to will be within bounds.
protected static int getParentIdx(int index)	Calculate and return the parent index of the parameter index. This method is irrelevant to what is currently in data and should not make any changes to data. You may assume index > 0.
protected static int getLeftChildIdx(int index)	Calculate and return the left child index of the parameter index. This method is irrelevant to what is currently in data and should not make any changes to data. You may assume index >= 0.
protected static int getRightChildIdx(int index)	Calculate and return the right child index of the parameter index. This method is irrelevant to what is currently in data and should not make any changes to data. You may assume index >= 0.
protected int getMinChildIdx(int index)	Return the index of the smaller child of the element at index. If the two children are equal, return the index of the left child. If the node at index is a leaf (has no children), return -1. Note that it's also possible for a single node in our heap to have only one child. In this case, return the index of the left child (we know that this is a heap so all nodes are as far left as possible) You may assume that index will be within bounds. getMinChildIndex depends on what is currently in data, but does not make any changes to data.
protected void percolateUp(int index)	Percolate the element at index up until no heap properties are violated by this element (the heap properties will not be violated once this element's parent is not greater than it). Do this by swapping the element with its parent as needed. Note the case where the element that you are percolating is equal to the parent. In this case, the heap property requiring that a node be no greater than its children is already satisfied, so you should not swap the element you are percolating with the parent. You may assume that index will be within bounds. percolateUp makes changes in data.
protected void percolateDown(int index)	Percolate the element at index down until no heap properties are violated by this element (the heap properties will not be violated once this element is not greater than its children). If swapping is needed, always swap places with the smaller child. If both children are equal and swapping is needed, swap with the left child. Note the case where the element that you are percolating is equal to the smaller child. In this case, the heap property requiring that a node be no greater than its children is already satisfied, so you should not swap the element you are percolating with the child. You may assume that index will be within bounds. percolateDown makes changes in data.
protected E deleteIndex(int index)	Remove the element at index from data and return it. If we are removing the last element then the heap properties are maintained. In other cases, we will replace the deleted element with the last element in the heap (the right-most node in the bottom-most level of the heap) to fix the completeness property. Then, either percolate this element down or percolate this element up as necessary until no heap properties are violated by this element (only one of these actions will be necessary to maintain the heap property, all fixes to the key order property should be by percolating the replacement element). The deleteIndex explanation can be found in the Appendix You can assume that index will be within bounds. deleteIndex makes changes in data.

Core Methods:

Method Name	Description
public void insert(E element)	Add element to the end of the heap (so that it is the right-most element in the bottom-most level) and percolate only the inserted element up until no heap properties are violated (all fixes to the heap properties should be by this percolation). Throw a NullPointerException and do not add to the heap if element is null. The insertion explanation can be found in the Appendix
public E getMin()	Return the root (this will be the smallest) element of the heap. If the heap is empty, return null instead.
public E remove()	Remove and return the root (this will be the smallest) element in the heap. Use deleteIndex() helper method here. If the heap is empty, return null instead.
public int size()	Return the number of elements in this min-heap.
public void clear()	Clear out the entire heap (the heap should be empty after this call).