You can study the average performance of the first step in a heap sort-building the initial heap-by taking the following steps:
• Modify the method reheap so that it returns the number of calls made to compareTo.
• Write a program that will iterate 1000 times. During each iteration, generate n random values and place them into an array. Count the number of comparisons needed by the code given in Exercise 7 to convert the array into a heap. Add the number of comparisons in each iteration into a total. After the loop has ended, compute the average number of comparisons needed to build the heap by dividing the number of comparisons by 1000.
• In the previous step, let n = 10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 200, 400, and 800. For each n, see whether the average number of calls to compareTo is greater than or equal to the lower bound n - 1 (see Exercise 7) and less than or equal to the upper bound n log2 n