This is java. Please use Heap.sort() function from algs4.jar

In the recorded lectures, Sedgewick claims that the construction phase of heapsort takes linear time. Let's see it in action. Place your code in a files called MyHeapSort.java.

One way to implement sort with a heap is to add N items into a min-heap (that's the "construction" phase of sorting), then remove those items. They'll come out in sorted order. Implement this approach for N random integers, where N = 103, 106, and 109. What is the time spent in the construction phase and the removal phase for these input sizes? Do these agree with the expected rate of runtime growth?

A better way to construct the heap is provided in Algorithm 2.7 of the book (p.324), and can be copied from algs4.jar in the Heap.sort() function. Answer the same questions (time spent, and agreement with theory). In particular, what percentage of time does heapsort spend in the construction phase for N = 104, 106, and 108.