Instance variables:

Instance Variable	Description
public 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).

You have to import Java's ArrayList in MyMinHeap.java

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 c)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. Thus, the methods that call them should make sure that only valid indices are passed as arguments to the helper methods and/or whether the value returned by these helper methods is within bounds.

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 do not need to check if from and to are out of bounds.
protected 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 do not need to check if index > 0
protected 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 do not need to check if index >= 0
protected 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 do not need to check if 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 can assume that index will be within bounds 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). This can be done 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 can assume that index will be within bounds 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 can assume that index will be within bounds 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 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)