NOTE: Could not fit all code into the text box; images attached are what remains of the problem.
**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; } 
/* ******* ***************************** Helper functions to restore the heap invariant. ***********/ 970 98 99 100 1010 102 103 104 105 106 1076 108 109 110 111 112 113 114 115 1160 117 private void aSwim (int k) { while (k > 1 && aGreater (k / 2, k)) { aExch (k, k / 2); k = k / 2; } } private void aSink (int k) { while (2 * k 1 && bless (k / 2, k)) { bExch (k, k / 2); k = k / 2; } } private void bSink (int k) { while (2 * k 0; } private boolean bless (int i, int i) { return b[i].compareTo (b[j]) N) return true; int left = 2 * k, right = 2 * K + 1; if (left N) return true; int left = 2 * k, right = 2 + k + 1; //Stdout.format ("checkmin: %s %s %s ", a[k], a[left], a[right]); if (left * The iterator doesn't implement
remove() since it's optional. public Iterator
iterator () { return new HeapIterator (); } private class HeapIterator implements Iterator { // create a new pg private MyMinMaxPQ copy; // add all items to copy of heap // takes linear time since already in heap order so no keys move public HeapIterator () { copy = new MyMinMaxPQ (size ()); for (int i = 1; i 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; } 257 258 259 2600 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 2850 286 private static void randomOps (MyMinMaxPQ pq, int NUMOPS, boolean log) { for (int i=NUMOPS; i>o; 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 ( !p.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 (!na.isEmpty()) 2850 286 287 288 289 290 291 292 293 294 295 296 297 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; 298 299 300 301 3020 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 } private static boolean assertionsAreOn () { Stdout.println ("ASSERTIONS ARE ON!"); return true; } public static void main (String[] args) { StdRandom.setSeed (); for (int i=100; i>0; i--) { MyMinMaxPQ pq = randomPQ (10); randomOps (p9, 10, true); randomEmpty (pq, true); } for (int i=100; i>o; 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(); 1/MyMinMaxPQ pq = new MyMinMaxPQ (100); //StdIn.fromString ("10 20 30 40 50 + - + 05 25 35 - + - 70 80 05 + - - + "); // This is not a very good test //StdIn.fromString ("10 20 40 50 30 + 70 60 - 30 - 50 20 +"); // This is a good test //while (!StdIn.isEmpty () { pq.showHeap (); String item = stdin.readString(); if (item.equals ("-")) Stdout.println ("min: " + pq.delMin (); 11 else if (item.equals ("+")) Stdout.println ("max: + pq.delMax (); 331 332 333 334 335 336 337 338 } // if (item.equals ("-")) Stdout.println ("min: + pq.delMin ()); 1/ else if (item.equals ("+")) Stdout.println ("max: + pq.delMax ()); // else pq.insert (Integer.parseInt (item)); //} //Stdout.println ("(" + pq.size () + left on pg)"); } } /* ******* ***************************** Helper functions to restore the heap invariant. ***********/ 970 98 99 100 1010 102 103 104 105 106 1076 108 109 110 111 112 113 114 115 1160 117 private void aSwim (int k) { while (k > 1 && aGreater (k / 2, k)) { aExch (k, k / 2); k = k / 2; } } private void aSink (int k) { while (2 * k 1 && bless (k / 2, k)) { bExch (k, k / 2); k = k / 2; } } private void bSink (int k) { while (2 * k 0; } private boolean bless (int i, int i) { return b[i].compareTo (b[j]) N) return true; int left = 2 * k, right = 2 * K + 1; if (left N) return true; int left = 2 * k, right = 2 + k + 1; //Stdout.format ("checkmin: %s %s %s ", a[k], a[left], a[right]); if (left * The iterator doesn't implement remove() since it's optional. public Iterator iterator () { return new HeapIterator (); } private class HeapIterator implements Iterator { // create a new pg private MyMinMaxPQ copy; // add all items to copy of heap // takes linear time since already in heap order so no keys move public HeapIterator () { copy = new MyMinMaxPQ (size ()); for (int i = 1; i 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; } 257 258 259 2600 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 2850 286 private static void randomOps (MyMinMaxPQ pq, int NUMOPS, boolean log) { for (int i=NUMOPS; i>o; 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 ( !p.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 (!na.isEmpty()) 2850 286 287 288 289 290 291 292 293 294 295 296 297 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; 298 299 300 301 3020 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 } private static boolean assertionsAreOn () { Stdout.println ("ASSERTIONS ARE ON!"); return true; } public static void main (String[] args) { StdRandom.setSeed (); for (int i=100; i>0; i--) { MyMinMaxPQ pq = randomPQ (10); randomOps (p9, 10, true); randomEmpty (pq, true); } for (int i=100; i>o; 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(); 1/MyMinMaxPQ pq = new MyMinMaxPQ (100); //StdIn.fromString ("10 20 30 40 50 + - + 05 25 35 - + - 70 80 05 + - - + "); // This is not a very good test //StdIn.fromString ("10 20 40 50 30 + 70 60 - 30 - 50 20 +"); // This is a good test //while (!StdIn.isEmpty () { pq.showHeap (); String item = stdin.readString(); if (item.equals ("-")) Stdout.println ("min: " + pq.delMin (); 11 else if (item.equals ("+")) Stdout.println ("max: + pq.delMax (); 331 332 333 334 335 336 337 338 } // if (item.equals ("-")) Stdout.println ("min: + pq.delMin ()); 1/ else if (item.equals ("+")) Stdout.println ("max: + pq.delMax ()); // else pq.insert (Integer.parseInt (item)); //} //Stdout.println ("(" + pq.size () + left on pg)"); } }
