This is java. Please use Use MaxPQ from the algs4.jar to build this

(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?

MaxPQ.java

/******************************************************************************  * Compilation: javac MaxPQ.java  * Execution: java MaxPQ < input.txt  * Dependencies: StdIn.java StdOut.java  * Data files: https://algs4.cs.princeton.edu/24pq/tinyPQ.txt  *   * Generic max priority queue implementation with a binary heap.  * Can be used with a comparator instead of the natural order,  * but the generic Key type must still be Comparable.  *  * % java MaxPQ < tinyPQ.txt   * Q X P (6 left on pq)  *  * We use a one-based array to simplify parent and child calculations.  *  * Can be optimized by replacing full exchanges with half exchanges  * (ala insertion sort).  *  ******************************************************************************/ import java.util.Comparator; import java.util.Iterator; import java.util.NoSuchElementException; /**  * The {@code MaxPQ} class represents a priority queue of generic keys.  * It supports the usual insert and delete-the-maximum  * operations, along with methods for peeking at the maximum key,  * testing if the priority queue is empty, and iterating through  * the keys.  * 
  * This implementation uses a binary heap.  * The insert and delete-the-maximum operations take  * logarithmic amortized time.  * The max, size, and is-empty operations take constant time.  * Construction takes time proportional to the specified capacity or the number of  * items used to initialize the data structure.  * 
  * For additional documentation, see Section 2.4 of  * Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.  *  * @author Robert Sedgewick  * @author Kevin Wayne  *  * @param  the generic type of key on this priority queue  */ public class MaxPQ implements Iterable { private Key[] pq; // store items at indices 1 to n private int n; // number of items on priority queue private Comparator comparator; // optional comparator /**  * Initializes an empty priority queue with the given initial capacity.  *  * @param initCapacity the initial capacity of this priority queue  */ public MaxPQ(int initCapacity) { pq = (Key[]) new Object[initCapacity + 1]; n = 0; } /**  * Initializes an empty priority queue.  */ public MaxPQ() { this(1); } /**  * Initializes an empty priority queue with the given initial capacity,  * using the given comparator.  *  * @param initCapacity the initial capacity of this priority queue  * @param comparator the order in which to compare the keys  */ public MaxPQ(int initCapacity, Comparator comparator) { this.comparator = comparator; pq = (Key[]) new Object[initCapacity + 1]; n = 0; } /**  * Initializes an empty priority queue using the given comparator.  *  * @param comparator the order in which to compare the keys  */ public MaxPQ(Comparator comparator) { this(1, comparator); } /**  * Initializes a priority queue from the array of keys.  * Takes time proportional to the number of keys, using sink-based heap construction.  *  * @param keys the array of keys  */ public MaxPQ(Key[] keys) { n = keys.length; pq = (Key[]) new Object[keys.length + 1]; for (int i = 0; i < n; i++) pq[i+1] = keys[i]; for (int k = n/2; k >= 1; k--) sink(k); assert isMaxHeap(); } /**  * Returns true if this priority queue is empty.  *  * @return {@code true} if this priority queue is empty;  * {@code false} otherwise  */ public boolean isEmpty() { return n == 0; } /**  * Returns the number of keys on this priority queue.  *  * @return the number of keys on this priority queue  */ public int size() { return n; } /**  * Returns a largest key on this priority queue.  *  * @return a largest key on this priority queue  * @throws NoSuchElementException if this priority queue is empty  */ public Key max() { if (isEmpty()) throw new NoSuchElementException("Priority queue underflow"); return pq[1]; } // helper function to double the size of the heap array private void resize(int capacity) { assert capacity > n; Key[] temp = (Key[]) new Object[capacity]; for (int i = 1; i <= n; i++) { temp[i] = pq[i]; } pq = temp; } /**  * Adds a new key to this priority queue.  *  * @param x the new key to add to this priority queue  */ public void insert(Key x) { // double size of array if necessary if (n == pq.length - 1) resize(2 * pq.length); // add x, and percolate it up to maintain heap invariant pq[++n] = x; swim(n); assert isMaxHeap(); } /**  * Removes and returns a largest key on this priority queue.  *  * @return a largest key on this priority queue  * @throws NoSuchElementException if this priority queue is empty  */ public Key delMax() { if (isEmpty()) throw new NoSuchElementException("Priority queue underflow"); Key max = pq[1]; exch(1, n--); sink(1); pq[n+1] = null; // to avoid loiterig and help with garbage collection if ((n > 0) && (n == (pq.length - 1) / 4)) resize(pq.length / 2); assert isMaxHeap(); return max; } /***************************************************************************  * Helper functions to restore the heap invariant.  ***************************************************************************/ private void swim(int k) { while (k > 1 && less(k/2, k)) { exch(k, k/2); k = k/2; } } private void sink(int k) { while (2*k <= n) { int j = 2*k; if (j < n && less(j, j+1)) j++; if (!less(k, j)) break; exch(k, j); k = j; } } /***************************************************************************  * Helper functions for compares and swaps.  ***************************************************************************/ private boolean less(int i, int j) { if (comparator == null) { return ((Comparable) pq[i]).compareTo(pq[j]) < 0; } else { return comparator.compare(pq[i], pq[j]) < 0; } } private void exch(int i, int j) { Key swap = pq[i]; pq[i] = pq[j]; pq[j] = swap; } // is pq[1..N] a max heap? private boolean isMaxHeap() { return isMaxHeap(1); } // is subtree of pq[1..n] rooted at k a max heap? private boolean isMaxHeap(int k) { if (k > n) return true; int left = 2*k; int right = 2*k + 1; if (left <= n && less(k, left)) return false; if (right <= n && less(k, right)) return false; return isMaxHeap(left) && isMaxHeap(right); } /***************************************************************************  * Iterator.  ***************************************************************************/ /**  * Returns an iterator that iterates over the keys on this priority queue  * in descending order.  * The iterator doesn't implement {@code remove()} since it's optional.  *  * @return an iterator that iterates over the keys in descending order  */ public Iterator iterator() { return new HeapIterator(); } private class HeapIterator implements Iterator { // create a new pq private MaxPQ copy; // add all items to copy of heap // takes linear time since already in heap order so no keys move public HeapIterator() { if (comparator == null) copy = new MaxPQ(size()); else copy = new MaxPQ(size(), comparator); for (int i = 1; i <= n; i++) copy.insert(pq[i]); } public boolean hasNext() { return !copy.isEmpty(); } public void remove() { throw new UnsupportedOperationException(); } public Key next() { if (!hasNext()) throw new NoSuchElementException(); return copy.delMax(); } } /**  * Unit tests the {@code MaxPQ} data type.  *  * @param args the command-line arguments  */ public static void main(String[] args) { MaxPQ pq = new MaxPQ(); while (!StdIn.isEmpty()) { String item = StdIn.readString(); if (!item.equals("-")) pq.insert(item); else if (!pq.isEmpty()) StdOut.print(pq.delMax() + " "); } StdOut.println("(" + pq.size() + " left on pq)"); }