Please help me with this algorithm lab using JAVA and also please don't post the one already in the data base because that one does not ask the user to enter a positive integer to call it n and generate n random integers. Thank you so much.

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).