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.

Heap.sort() please use this code

/******************************************************************************  * Compilation: javac Heap.java  * Execution: java Heap < input.txt  * Dependencies: StdOut.java StdIn.java  * Data files: https://algs4.cs.princeton.edu/24pq/tiny.txt  * https://algs4.cs.princeton.edu/24pq/words3.txt  *   * Sorts a sequence of strings from standard input using heapsort.  *  * % more tiny.txt  * S O R T E X A M P L E  *  * % java Heap < tiny.txt  * A E E L M O P R S T X [ one string per line ]  *  * % more words3.txt  * bed bug dad yes zoo ... all bad yet  *  * % java Heap < words3.txt  * all bad bed bug dad ... yes yet zoo [ one string per line ]  *  ******************************************************************************/ /**  * The {@code Heap} class provides a static methods for heapsorting  * an array.  * 
  * For additional documentation, see Section 2.4 of  * Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.  *  * @author Robert Sedgewick  * @author Kevin Wayne  */ public class Heap { // This class should not be instantiated. private Heap() { } /**  * Rearranges the array in ascending order, using the natural order.  * @param pq the array to be sorted  */ public static void sort(Comparable[] pq) { int n = pq.length; for (int k = n/2; k >= 1; k--) sink(pq, k, n); while (n > 1) { exch(pq, 1, n--); sink(pq, 1, n); } } /***************************************************************************  * Helper functions to restore the heap invariant.  ***************************************************************************/ private static void sink(Comparable[] pq, int k, int n) { while (2*k <= n) { int j = 2*k; if (j < n && less(pq, j, j+1)) j++; if (!less(pq, k, j)) break; exch(pq, k, j); k = j; } } /***************************************************************************  * Helper functions for comparisons and swaps.  * Indices are "off-by-one" to support 1-based indexing.  ***************************************************************************/ private static boolean less(Comparable[] pq, int i, int j) { return pq[i-1].compareTo(pq[j-1]) < 0; } private static void exch(Object[] pq, int i, int j) { Object swap = pq[i-1]; pq[i-1] = pq[j-1]; pq[j-1] = swap; } // print array to standard output private static void show(Comparable[] a) { for (int i = 0; i < a.length; i++) { StdOut.println(a[i]); } } /**  * Reads in a sequence of strings from standard input; heapsorts them;   * and prints them to standard output in ascending order.   *  * @param args the command-line arguments  */ public static void main(String[] args) { String[] a = StdIn.readAllStrings(); Heap.sort(a); show(a); } }