java - data structure - please without importing things other than scanner

public class maxHeap { public class Node { private int key; private Node(int k) {key =k;} } private Node[] heapArray; private int maxSize; private int currentSize; public maxHeap(int capacity) { maxSize = capacity; currentSize = 0; heapArray = new Node[maxSize]; } public boolean isEmpty() { return currentSize ==0;} public boolean isFull() { return currentSize == maxSize;} public boolean hasLeft(int index) { return ((2*index + 1

public boolean insert(int k) { if(isFull()) return false; Node newest = new Node(k); //add node to the end of the heap heapArray[currentSize] = newest; reheapUp(currentSize); //currentSize is the the index where we add the new node currentSize++; return true; } public void reheapUp(int index) { int parent = (index -1)/2; Node bottom = heapArray[index]; //loop until the correct position of the new node is found while (index >0 && heapArray[parent].key heapArray[leftChild].key ) largeChild = rightChild; }//end of outer if if(top.key>= heapArray[largeChild].key) break; //we found the correct position heapArray[index] = heapArray[largeChild]; //move the largest child up index = largeChild; }//end of while heapArray[index] = top; }//end of reheapDown public boolean updateKey(int index, int newKey) { //invalid index if (index = currentSize) return false; int oldKey = heapArray[index].key; heapArray[index].key = newKey; if(newKey > oldKey) reheapUp(index); //move the key up else reheapDown(index); //move the key down return true; }//end of update key }

Q2. Write the following functions: (you can reuse some of the methods in the maxheap class we implemented) 1. Build MaxHeap(int []): which takes an unordered array, convert it to a heap and return the maxheap array. Note that you will not have a current size variable as in the heap class. You array is full with elements (i.e. currentSize = array length). 2. heapsort(): which uses buildMaxHeap(), then sort and return the array. 3. simpleSort(): which is a simple sorting algorithm that compares every two adjacent elements (every two elements next to each other) and swap if needed until the array is sorted. It starts with the element at index 0 up to the last element in the array. Example: given the array (5,1,4,2,8) First Pass: (51 4 2 8 )-> (1 5 4 2 8 ), Here, algorithm compares the first two elements, and swaps since 5 > 1. (1 5 4 2 8 )-> (14 5 28 ), Swap since 5 > 4 (1 4 5 2 8 ) -> ( 14 2 5 8 ), Swap since 5 > 2 (142 58 ) -> ( 14 2 5 8 ), Now, since these elements are already in order (8 > 5), algorithm does not swap them. Second Pass: (1 4 2 5 8 )-> (1 4 2 58) (1 4 2 5 8 )-> (1 245 8 ), Swap since 4 > 2 (1 24 5 8 )-> (1 24 58 ) (1245 8 )-> (1 24 5 8 ) Now, the array is already sorted, but our algorithm does not know if it is completed. The algorithm needs one whole pass without any swap to know it is sorted. Third Pass: (12458)-> (12458) (12458)-> (12458) (12458 )-> (12458) (12458 )-> (12458) In your main: Create an array of integers and fill it with random 100,000 numbers. Create a copy of the same array (you can use arraycopy(). For example: import java.lang. System; int[] a = {10,15,3,5,12,8,89,55,33}; int []b = new int[a. length]; System.arraycopy(a, , b, 0, a.length); Use heapsort() and simpleSort() to sort the array. Pass the original array to the first function and the copy to the second function. Log and print the time taken by each function. Note: Test your code first with a small array size, make sure your sorting functions work by printing the sorted array Remove the printing statements and run your code with a very large array If your machine was not able to handle 100,000 elements, run your code with an array of size 10,000, or 1000 Sample output: Test 1: small size array Array before sorting: 10 15 3 5 12 8 89 55 33 After heap sort: 3 5 8 10 12 15 33 55 89 Array before sorting: 10 15 3 5 12 8 89 55 33 After simple sort: 3 5 8 10 12 15 33 55 89 Test2: Sample output with 100,000 elements array: HeapSort: HeapSort took 34 ms simpleSort: simpleSort took 22302 ms