Data Structure / Language java

Q2. Write the following functions: (you can reuse some of the methods in the maxheap class we implemented) 1. BuildMaxHeap(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. (15428) -> (1 4 5 2 8 ), Swap since 5 > 4 (1 4 5 2 8 )-> (14 2 58), Swap since 5 > 2 ( 14 2 5 8 ) -> ( 1 4 2 5 8 ), Now, since these elements are already in order (8 > 5), algorithm does not swap them. Second Pass: (142 58 )-> (1 4 2 58) (14258 )-> (12458), Swap since 4 > 2 (12458)-> (12458) (124 58 )-> (12458) 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) (1 2 458 )-> (12458) (12458)-> (12458) (1 2 458 )-> (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, a, b, e, 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