Programming assignment 6.
NOTE: You are NOT allowed to define a new array in any part of the code.
Create the following functions: build_MaxHeap, max_heapify, heap_sort.
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 function to sort the array. In order to sort the array using heapsort, you need to follow the
below steps:
3.1 Build a max-heap (call the function build_Maxheap). In order to build the max-heap follow the below
pseudocode:
% 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, n-1, n-2,.., 1, Can we start from n/2 instead of n? Why????
a(1:i) = max_heapify(a,i); % a(1:i) = contains a[1] a[2] …a[i] (You could have a flag for
the i too! (Assume that i is the index of the last element of the array! 😊)
end
3.2 Keep removing the roots (first element in a) one by one until the tree/array becomes empty.
4. Determine the average-running time of heap_sort function for n=1000, and 100 repetitions.
5. Compare your answer with the average-running time of selection sort (you need implement it).
