Please help me with this algorithm lab using JAVA, Thank you!

Create three functions named build_MaxHeap(a),max_heapify(a,i), heap_sort(a).

1.Request the user to enter a positive integer, and call it n.

2.Generate n random integers between -10000 to 10000 and save them in array a.

3.Call heap_sort (a)function to sort the array.In order to sort the array using heapsort, you need to follow the below steps:

3.1Build a max-heap (call the function build_heap(a)). In order to build the max-heap follow thebelowpseudocode

:

%new_a is the output of the function, if you are using any other programming language, please write % return new_a at the end of your code.

a=build_MaxHeap(a)

n= length(a);

for i=n: -1:1

% i= n downto 1 , Can we start from n/2 instead of n? Why????

a =max_heapify(a,i);

end

3.2 Remove the root (remove the first element in a) :

4.Determine theaverage-running time of heap_sortfunction forn=10000, and100 repetitions.

5.Compare your answer with the average-running time of quicksort and selection sort(you need implement it).