This is java

(1) Write a performance driver client program, PQtester.java, that uses insert to add N elements to a priority queue, then uses remove the maximum to remove half the keys, then uses insert to fill it up again, then uses remove the maximum to remove all the keys. Use MaxPQ from the algs4.jar.

Write your driver to do this multiple times on random sequences of keys, with N varying from small to large. Do a few runs for each value of N, so you can compute an average, and get a sense of reproducibility. Your driver should measure the time taken for each run, and print-out or plot the average running times. I suggest using System.nanoTime() to capture runtime.

Show your table of run times in the README. What are reasonable values of "small" and "large" values of N?

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

(3) Run empirical studies to compute the average and standard deviation of the average length of a path to a random node in a BST built by insertion of N random keys into an initially empty tree, for N from 100 to 12,800 (with N doubling from 100, 200, 400 ...) Details: - I recommend developing your own BST implementation in MyBST.java, building on the code in the BST class provided in algs4.jar. - For each tree size, do 1000 trial trees. That means: create an empty BST object, generate N keys, and put them into the BST. - Once you have a filled BST, the average path length on this tree (mt) is the sum of all node depths divided by the number of nodes, plus 1. You'll need to create a function in your BST implementation to compute and return this. - I'm asking you to compute the average and standard deviations of those mt values. - Print those values to a table, captured in your README file