Source code

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}