**Implement the function bodies where it says TODO**

// Exercise 2.4.29 package Homework; import stdlib.*; import java.util.Iterator; import java.util.NoSuchElementException;

public class hw8 { // To turn on assertions for a program in eclipse, // run the program once, then go to the menubar and select // Run > Run Configurations... > Arguments > VM Arguments // And add // -ea // As a VM argument public static class MyMinMaxPQ> implements Iterable { private int N; // number of items on priority queue private int MAXN; // size of the the arrays private K[] a; // minheap private K[] b; // maxheap // the array ab maps from a to b // the array ba maps from b to a // they are inverses, so i == ba[ab[i]] == ab[ba[i]] for any i // private int[] ab; // index a to b: a[i] == b[ab[i]] private int[] ba; // index b to a: b[i] == a[ba[i]] @SuppressWarnings("unchecked") /** Create an empty priority queue with the given initial capacity, using the given comparator. */ public MyMinMaxPQ (int capacity) { MAXN = capacity; a = (K[]) new Comparable[MAXN + 1]; b = (K[]) new Comparable[MAXN + 1]; ab = new int[MAXN + 1]; ba = new int[MAXN + 1]; N = 0; } /** Is the priority queue empty? */ public boolean isEmpty () { return N == 0; } /** Is the priority queue full? */ public boolean isFull () { return N == MAXN; } /** Return the number of items on the priority queue. */ public int size () { return N; } /** * Return the smallest key on the priority queue. Throw an exception if the * priority queue is empty. */ public K min () { if (isEmpty ()) throw new Error ("Priority queue underflow"); return a[1]; } /** Add a new key to the priority queue. */ public void insert (K x) { if (isFull ()) throw new Error ("Priority queue overflow"); // add x, and percolate it up to maintain heap invariant N++; a[N] = x; b[N] = x; ab[N] = N; ba[N] = N; aSwim (N); bSwim (N); assert isMinMaxHeap (); } /** * Delete and return the smallest key on the priority queue. Throw an * exception if the priority queue is empty. */ public K delMin () { if (N == 0) throw new Error ("Priority queue underflow"); // TODO K minimum = null; assert isMinMaxHeap (); return minimum; } /** * Delete and return the largest key on the priority queue. Throw an * exception if the priority queue is empty. */ public K delMax () { if (N == 0) throw new Error ("Priority queue underflow"); // TODO K maximum = null; assert isMinMaxHeap (); return maximum; } private static int randomValue() { return StdRandom.uniform (100); } private static MyMinMaxPQ randomPQ (int maxSize) { int minCapacity = 5; int capacity = StdRandom.uniform(maxSize)+minCapacity; MyMinMaxPQ pq = new MyMinMaxPQ<> (capacity); for (int i=StdRandom.uniform (capacity); i>0; i--) pq.insert (randomValue()); return pq; } private static void randomOps (MyMinMaxPQ pq, int NUMOPS, boolean log) { for (int i=NUMOPS; i>0; i--) { switch (StdRandom.uniform (4)) { case 0: if (! pq.isEmpty()) { Integer x = pq.delMin(); if (log) { StdOut.format ("delMin=%d ", x); pq.showHeap(); } } break; case 1: if ( !pq.isEmpty()) { Integer x = pq.delMax(); if (log) { StdOut.format ("delMax=%d ", x); pq.showHeap(); } } break; default: if (! pq.isFull()) { int x = randomValue(); pq.insert(x); if (log) { StdOut.format ("insert=%d ", x); pq.showHeap(); } } break; } } } private static void randomEmpty (MyMinMaxPQ pq, boolean log) { while (! pq.isEmpty ()) switch (StdRandom.uniform (2)) { case 0: if (! pq.isEmpty()) { Integer x = pq.delMin(); if (log) { StdOut.format ("delMin=%d ", x); pq.showHeap(); } } break; case 1: if (! pq.isEmpty()) { Integer x = pq.delMax(); if (log) { StdOut.format ("delMax=%d ", x); pq.showHeap(); } } break; } } private static boolean assertionsAreOn () { StdOut.println ("ASSERTIONS ARE ON!"); return true; } public static void main (String[] args) { StdRandom.setSeed (0); for (int i=100; i>0; i--) { MyMinMaxPQ pq = randomPQ (10); randomOps (pq, 10, true); randomEmpty (pq, true); } for (int i=100; i>0; i--) { MyMinMaxPQ pq = randomPQ (1000); randomOps (pq, 10000, false); randomEmpty (pq, false); } StdOut.println ("If you don't see a statement below saying that assertions are on, then they are not on."); StdOut.println ("That means that you have not really tested anything!"); StdOut.println ("You must enable assertions!"); StdOut.println ("To enable assertions, see the instructions at the top of this .java file."); assert assertionsAreOn();