001// Exercise 2.4.29 002package algs24; 003import stdlib.*; 004import java.util.Iterator; 005import java.util.NoSuchElementException; 006 007// To turn on assertions for a program in eclipse, 008// run the program once, then go to the menubar and select 009// Run > Run Configurations... > Arguments > VM Arguments 010// And add 011// -ea 012// As a VM argument 013public class MyMinMaxPQ<K extends Comparable<? super K>> implements Iterable<K> { 014 private int N; // number of items on priority queue 015 private int MAXN; // size of the the arrays 016 private K[] a; // minheap 017 private K[] b; // maxheap 018 019 // the array ab maps from a to b 020 // the array ba maps from b to a 021 // they are inverses, so i == ba[ab[i]] == ab[ba[i]] for any i 022 // 023 private int[] ab; // index a to b: a[i] == b[ab[i]] 024 private int[] ba; // index b to a: b[i] == a[ba[i]] 025 026 027 @SuppressWarnings("unchecked") 028 /** Create an empty priority queue with the given initial capacity, using the given comparator. */ 029 public MyMinMaxPQ (int capacity) { 030 MAXN = capacity; 031 a = (K[]) new Comparable[MAXN + 1]; 032 b = (K[]) new Comparable[MAXN + 1]; 033 ab = new int[MAXN + 1]; 034 ba = new int[MAXN + 1]; 035 N = 0; 036 } 037 038 /** Is the priority queue empty? */ 039 public boolean isEmpty () { return N == 0; } 040 041 /** Is the priority queue full? */ 042 public boolean isFull () { return N == MAXN; } 043 044 /** Return the number of items on the priority queue. */ 045 public int size () { return N; } 046 047 /** 048 * Return the smallest key on the priority queue. Throw an exception if the 049 * priority queue is empty. 050 */ 051 public K min () { 052 if (isEmpty ()) throw new Error ("Priority queue underflow"); 053 return a[1]; 054 } 055 056 /** Add a new key to the priority queue. */ 057 public void insert (K x) { 058 if (isFull ()) throw new Error ("Priority queue overflow"); 059 // add x, and percolate it up to maintain heap invariant 060 N++; 061 a[N] = x; 062 b[N] = x; 063 ab[N] = N; 064 ba[N] = N; 065 aSwim (N); 066 bSwim (N); 067 assert isMinMaxHeap (); 068 } 069 070 /** 071 * Delete and return the smallest key on the priority queue. Throw an 072 * exception if the priority queue is empty. 073 */ 074 public K delMin () { 075 if (N == 0) throw new Error ("Priority queue underflow"); 076 // TODO 077 assert isMinMaxHeap (); 078 return null; 079 } 080 /** 081 * Delete and return the largest key on the priority queue. Throw an 082 * exception if the priority queue is empty. 083 */ 084 public K delMax () { 085 if (N == 0) throw new Error ("Priority queue underflow"); 086 // TODO 087 assert isMinMaxHeap (); 088 return null; 089 } 090 091 /* ********************************************************************* 092 * Helper functions to restore the heap invariant. 093 **********************************************************************/ 094 095 private void aSwim (int k) { 096 while (k > 1 && aGreater (k / 2, k)) { 097 aExch (k, k / 2); 098 k = k / 2; 099 } 100 } 101 private void aSink (int k) { 102 while (2 * k <= N) { 103 int j = 2 * k; 104 if (j < N && aGreater (j, j + 1)) j++; 105 if (!aGreater (k, j)) break; 106 aExch (k, j); 107 k = j; 108 } 109 } 110 private void bSwim (int k) { 111 while (k > 1 && bLess (k / 2, k)) { 112 bExch (k, k / 2); 113 k = k / 2; 114 } 115 } 116 private void bSink (int k) { 117 while (2 * k <= N) { 118 int j = 2 * k; 119 if (j < N && bLess (j, j + 1)) j++; 120 if (!bLess (k, j)) break; 121 bExch (k, j); 122 k = j; 123 } 124 } 125 126 /* ********************************************************************* 127 * Helper functions for compares and swaps. 128 **********************************************************************/ 129 private boolean aGreater (int i, int j) { 130 return a[i].compareTo (a[j]) > 0; 131 } 132 private boolean bLess (int i, int j) { 133 return b[i].compareTo (b[j]) < 0; 134 } 135 private void swap (K[] a, int i, int j) { 136 K tmp = a[i]; 137 a[i] = a[j]; 138 a[j] = tmp; 139 } 140 private void swap (int[] a, int i, int j) { 141 int tmp = a[i]; 142 a[i] = a[j]; 143 a[j] = tmp; 144 } 145 private void aExch (int ai, int aj) { 146 int bi = ab[ai]; 147 int bj = ab[aj]; 148 swap (a, ai, aj); 149 swap (ab, ai, aj); 150 swap (ba, bi, bj); 151 } 152 private void bExch (int bi, int bj) { 153 int ai = ba[bi]; 154 int aj = ba[bj]; 155 swap (b, bi, bj); 156 swap (ab, ai, aj); 157 swap (ba, bi, bj); 158 } 159 160 private void showHeap () { 161 StdOut.print ("a: "); 162 for (int i = 1; i <= N; i++) 163 StdOut.print (a[i] + " "); 164 StdOut.println (); 165 StdOut.print ("b: "); 166 for (int i = 1; i <= N; i++) 167 StdOut.print (b[i] + " "); 168 StdOut.println (); 169 /* 170 * StdOut.print ("ab: "); for (int i = 1; i <= N; i++) StdOut.print 171 * (ab[i] + " "); StdOut.println (); StdOut.print ("ba: "); for (int i = 172 * 1; i <= N; i++) StdOut.print (ba[i] + " "); StdOut.println (); 173 */ 174 } 175 private void check () { 176 for (int i = 1; i <= N; i++) { 177 // a and b have the same data, mapped by ab and ba 178 assert a[i] == b[ab[i]]; 179 assert b[i] == a[ba[i]]; 180 // ab and ba are inverses 181 assert i == ab[ba[i]]; 182 assert i == ba[ab[i]]; 183 } 184 } 185 186 private boolean isMinMaxHeap () { 187 check (); 188 return isMaxHeap (1) && isMinHeap (1); 189 } 190 private boolean isMaxHeap (int k) { 191 if (k > N) return true; 192 int left = 2 * k, right = 2 * k + 1; 193 if (left <= N && bLess (k, left)) { StdOut.format ("Not a max heap k=%d left=%d\n", k, left); showHeap(); return false; } 194 if (right <= N && bLess (k, right)) { StdOut.format ("Not a max heap k=%d right=%d\n", k, right); showHeap(); return false; } 195 return isMaxHeap (left) && isMaxHeap (right); 196 } 197 private boolean isMinHeap (int k) { 198 if (k > N) return true; 199 int left = 2 * k, right = 2 * k + 1; 200 //StdOut.format ("checkmin: %s %s %s\n", a[k], a[left], a[right]); 201 if (left <= N && aGreater (k, left)) { StdOut.format ("Not a min heap k=%d left=%d\n", k, left); showHeap(); return false; } 202 if (right <= N && aGreater (k, right)) { StdOut.format ("Not a min heap k=%d right=%d\n", k, right); showHeap(); return false; } 203 return isMinHeap (left) && isMinHeap (right); 204 } 205 206 207 /* ********************************************************************* 208 * Iterator 209 **********************************************************************/ 210 211 /** 212 * Return an iterator that iterates over all of the keys on the priority 213 * queue in ascending order. 214 * <p> 215 * The iterator doesn't implement {@code remove()} since it's optional. 216 */ 217 public Iterator<K> iterator () { return new HeapIterator (); } 218 private class HeapIterator implements Iterator<K> { 219 // create a new pq 220 private MyMinMaxPQ<K> copy; 221 222 // add all items to copy of heap 223 // takes linear time since already in heap order so no keys move 224 public HeapIterator () { 225 copy = new MyMinMaxPQ<> (size ()); 226 for (int i = 1; i <= N; i++) 227 copy.insert (a[i]); 228 } 229 230 public boolean hasNext () { return !copy.isEmpty (); } 231 public void remove () { throw new UnsupportedOperationException (); } 232 public K next () { 233 if (!hasNext ()) throw new NoSuchElementException (); 234 return copy.delMin (); 235 } 236 } 237 238 /** 239 * A test client. 240 */ 241 private static int randomValue () { return StdRandom.uniform (100); } 242 private static MyMinMaxPQ<Integer> randomPQ (int maxSize) { 243 int minCapacity = 5; 244 int capacity = StdRandom.uniform(maxSize)+minCapacity; 245 MyMinMaxPQ<Integer> pq = new MyMinMaxPQ<> (capacity); 246 for (int i=StdRandom.uniform (capacity); i>0; i--) 247 pq.insert (randomValue()); 248 return pq; 249 } 250 private static void randomOps (MyMinMaxPQ<Integer> pq, int NUMOPS, boolean log) { 251 for (int i=NUMOPS; i>0; i--) { 252 switch (StdRandom.uniform (4)) { 253 case 0: 254 if (! pq.isEmpty()) { 255 int x = pq.delMin(); 256 if (log) { StdOut.format ("delMin=%d\n", x); pq.showHeap(); } 257 } 258 break; 259 case 1: 260 if (! pq.isEmpty()) { 261 int x = pq.delMax(); 262 if (log) { StdOut.format ("delMax=%d\n", x); pq.showHeap(); } 263 } 264 break; 265 default: 266 if (! pq.isFull()) { 267 int x = randomValue(); 268 pq.insert(x); 269 if (log) { StdOut.format ("insert=%d\n", x); pq.showHeap(); } 270 } 271 break; 272 } 273 } 274 } 275 private static void randomEmpty (MyMinMaxPQ<Integer> pq, boolean log) { 276 while (! pq.isEmpty ()) 277 switch (StdRandom.uniform (2)) { 278 case 0: 279 if (! pq.isEmpty()) { 280 int x = pq.delMin(); 281 if (log) { StdOut.format ("delMin=%d\n", x); pq.showHeap(); } 282 } 283 break; 284 case 1: 285 if (! pq.isEmpty()) { 286 int x = pq.delMax(); 287 if (log) { StdOut.format ("delMax=%d\n", x); pq.showHeap(); } 288 } 289 break; 290 } 291 } 292 private static boolean assertionsAreOn () { 293 StdOut.println ("ASSERTIONS ARE ON!"); 294 return true; 295 } 296 public static void main (String[] args) { 297 StdRandom.setSeed (0); 298 for (int i=100; i>0; i--) { 299 MyMinMaxPQ<Integer> pq = randomPQ (10); 300 randomOps (pq, 10, true); 301 randomEmpty (pq, true); 302 } 303 for (int i=100; i>0; i--) { 304 MyMinMaxPQ<Integer> pq = randomPQ (1000); 305 randomOps (pq, 10000, false); 306 randomEmpty (pq, false); 307 } 308 StdOut.println ("If you don't see a statement below saying that assertions are on, then they are not on."); 309 StdOut.println ("That means that you have not really tested anything!"); 310 StdOut.println ("You must enable assertions!"); 311 StdOut.println ("To enable assertions, see the instructions at the top of this .java file."); 312 assert assertionsAreOn(); 313 314 315 //MyMinMaxPQ<Integer> pq = new MyMinMaxPQ<> (100); 316 //StdIn.fromString ("10 20 30 40 50 + - + 05 25 35 - + - 70 80 05 + - - + "); // This is not a very good test 317 //StdIn.fromString ("10 20 40 50 30 + 70 60 - 30 - 50 20 +"); // This is a good test 318 //while (!StdIn.isEmpty ()) { 319 // pq.showHeap (); 320 // String item = StdIn.readString (); 321 // if (item.equals ("-")) StdOut.println ("min: " + pq.delMin ()); 322 // else if (item.equals ("+")) StdOut.println ("max: " + pq.delMax ()); 323 // else pq.insert (Integer.parseInt (item)); 324 //} 325 //StdOut.println ("(" + pq.size () + " left on pq)"); 326 } 327}