Create a class called MinHeap. Because elements need to be stored in a sorted manner, you can assume that any elements added to the tree implement the Comparable class with the appropriate generic type (see Binary Search Tree activity for more information):

Can you please complete and put together the following JAVA code:

Main Method:

public static void main(String[] arg){

MinHeapmh=new MinHeap(); mh.insert(2); mh.insert(4); mh.insert(1); mh.insert(10); mh.insert(3); mh.insert(6); mh.insert(15); mh.insert(12); mh.insert(16); mh.insert(5);

while(!mh.isEmpty()){

System.out.println(mh.remove());

}

public class MinHeap > { private E[] heap; private int size = 0; private static final int DEFAULT_CAPACITY = 8; public MinHeap(int capacity) { heap = (E[]) new Comparable[capacity]; } public MinHeap() { this(DEFAULT_CAPACITY); } public int size() { return _____; }

public boolean isEmpty() { return size() == _____; } private void expand() { E[] newHeap = (E[]) new Comparable[heap.length * 2]; for (int i = 0; i < size(); i++) { newHeap[i] = heap[i]; } heap = newHeap; } private void swapElements(int p1, int p2) { E temp = heap[p1]; heap[p1] = heap[p2]; heap[p2] = temp; }

private int getParentIndex(int childIndex) { // if odd, child is a left node if (childIndex % 2 != 0) { return childIndex / 2; } // if even, child is a right node else { return childIndex / 2 - 1; } } public void insert(E element) { int position = size(); if (position == heap.length) { expand(); } size++; heap[position] = element; int parent = getParentIndex(position);

while (position > 0 && heap[position].compareTo(heap[parent]) < 0) { // if parent is greater, swap parent and node swapElements(________, position); // update position of the new element and find next parent up position = getParentIndex(position); parent = getParentIndex(________); } } public E remove() { if (isEmpty()) { return null; } // take out root and place last node at root position E min = heap[0]; heap[____] = heap[size() - 1]; heap[size() - 1] = null; // optional size--; // position of new root and its smaller child int position = 0; int smallerChild = smallerChildIndex(position);

// while there is a smaller child, swap parent and child while (__________ != position) { swapElements(position, smallerChild); // update position of node and get new smaller child position = smallerChild; smallerChild = smallerChildIndex(_______); } return min; } }

Method for finding the smaller child element:

private int smallerChildIndex(int getParentIndex) { int smaller = getParentIndex; // get left child index int leftChild = 2 * getParentIndex + 1; // if the left child index is in bounds of the heap...

if (leftChild < size() - 1) {

// set smaller to left if left is smaller than parent smaller = heap[leftChild].compareTo(heap[smaller]) < 0

? leftChild : smaller; // get right child index int rightChild = 2 * getParentIndex + 2; // if the right child index is in bounds of the heap... if (rightChild < size() - 1) { // set smaller to right if right is smaller than parent smaller = heap[rightChild].compareTo(heap[smaller]) < 0 ? rightChild : smaller; } } return smaller; }

Input: 7, 3, 6, 2, 9, 1, 10, 4

What does the heap look like after all of the elements are added?

How many 'swap' operations must be performed when the value 1 is added (underlined above)?

if a remove operation is performed, which element initially becomes the root? Which children must it be swapped with (in order), to be placed in the correct position?