001// Exercise 2.4.15 (Solution published at http://algs4.cs.princeton.edu/) 002package algs24; 003import stdlib.*; 004import java.util.Comparator; 005import java.util.Iterator; 006import java.util.NoSuchElementException; 007/* *********************************************************************** 008 * Compilation: javac MaxPQ.java 009 * Execution: java MaxPQ < input.txt 010 * 011 * Generic max priority queue implementation with a binary heap. 012 * Can be used with a comparator instead of the natural order, 013 * but the generic key type must still be Comparable. 014 * 015 * % java MaxPQ < tinyPQ.txt 016 * Q X P (6 left on pq) 017 * 018 * We use a one-based array to simplify parent and child calculations. 019 * 020 *************************************************************************/ 021 022/** 023 * The {@code MaxPQ} class represents a priority queue of generic keys. 024 * It supports the usual <em>insert</em> and <em>delete-the-maximum</em> 025 * operations, along with methods for peeking at the maximum key, 026 * testing if the priority queue is empty, and iterating through 027 * the keys. 028 * <p> 029 * The <em>insert</em> and <em>delete-the-maximum</em> operations take 030 * logarithmic amortized time. 031 * The <em>max</em>, <em>size</em>, and <em>is-empty</em> operations take constant time. 032 * Construction takes time proportional to the specified capacity or the number of 033 * items used to initialize the data structure. 034 * <p> 035 * This implementation uses a binary heap. 036 * <p> 037 * For additional documentation, see <a href="http://algs4.cs.princeton.edu/24pq">Section 2.4</a> of 038 * <i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin Wayne. 039 */ 040public class MaxPQ<K extends Comparable<? super K>> implements Iterable<K> { 041 private K[] pq; // store items at indices 1 to N 042 private int N; // number of items on priority queue 043 private Comparator<? super K> comparator; // optional Comparator 044 045 // helper function to double the size of the heap array 046 @SuppressWarnings("unchecked") 047 private void resize(int capacity) { 048 if (capacity <= N) throw new IllegalArgumentException (); 049 K[] temp = (K[]) new Comparable[capacity]; 050 for (int i = 1; i <= N; i++) temp[i] = pq[i]; 051 pq = temp; 052 } 053 054 @SuppressWarnings("unchecked") 055 /** Create an empty priority queue with the given initial capacity, using the given comparator. */ 056 public MaxPQ(int initCapacity, Comparator<? super K> comparator) { 057 pq = (K[]) new Comparable[initCapacity + 1]; 058 N = 0; 059 this.comparator = comparator; 060 } 061 /** Create an empty priority queue with the given initial capacity. */ 062 public MaxPQ(int initCapacity) { this(initCapacity, null); } 063 /** Create an empty priority queue using the given comparator. */ 064 public MaxPQ(Comparator<? super K> comparator) { this(1, comparator); } 065 /** Create an empty priority queue. */ 066 public MaxPQ() { this(1, null); } 067 068 /** 069 * Create a priority queue with the given items. 070 * Takes time proportional to the number of items using sink-based heap construction. 071 */ 072 public MaxPQ(K[] keys) { 073 this(keys.length, null); 074 N = keys.length; 075 for (int i = 0; i < N; i++) 076 pq[i+1] = keys[i]; 077 for (int k = N/2; k >= 1; k--) 078 sink(k); 079 //assert isMaxHeap(); 080 } 081 082 /** Is the priority queue empty? */ 083 public boolean isEmpty() { return N == 0; } 084 085 /** Return the number of items on the priority queue. */ 086 public int size() { return N; } 087 088 /** 089 * Return the largest key on the priority queue. 090 * @throws java.util.NoSuchElementException if the priority queue is empty. 091 */ 092 public K max() { 093 if (isEmpty()) throw new NoSuchElementException("Priority queue underflow"); 094 return pq[1]; 095 } 096 097 /** Add a new key to the priority queue. */ 098 public void insert(K x) { 099 // double size of array if necessary 100 if (N >= pq.length - 1) resize(2 * pq.length); 101 102 // add x, and percolate it up to maintain heap invariant 103 pq[++N] = x; 104 swim(N); 105 //assert isMaxHeap(); 106 } 107 108 /** 109 * Delete and return the largest key on the priority queue. 110 * @throws java.util.NoSuchElementException if the priority queue is empty. 111 */ 112 public K delMax() { 113 if (isEmpty()) throw new NoSuchElementException("Priority queue underflow"); 114 exch(1, N); 115 N = N - 1; 116 sink(1); 117 K max = pq[N+1]; 118 pq[N+1] = null; // avoid loitering and help with garbage collection 119 if ((N > 0) && (N == (pq.length - 1) / 4)) resize(pq.length / 2); 120 //assert isMaxHeap(); 121 return max; 122 } 123 124 125 /* ********************************************************************* 126 * Helper functions to restore the heap invariant. 127 **********************************************************************/ 128 129 private void swim(int k) { 130 while (k > 1 && less(k/2, k)) { 131 exch(k, k/2); 132 k = k/2; 133 } 134 } 135 136 private void sink(int k) { 137 while (2*k <= N) { 138 int j = 2*k; 139 if (j < N && less(j, j+1)) j++; 140 if (!less(k, j)) break; 141 exch(k, j); 142 k = j; 143 } 144 } 145 146 /* ********************************************************************* 147 * Helper functions for compares and swaps. 148 **********************************************************************/ 149 private boolean less(int i, int j) { 150 if (comparator == null) { 151 return pq[i].compareTo(pq[j]) < 0; 152 } 153 else { 154 return comparator.compare(pq[i], pq[j]) < 0; 155 } 156 } 157 158 private void exch(int i, int j) { 159 if (DEBUG) GraphvizBuilder.binaryHeapToFile (pq, N); 160 K swap = pq[i]; 161 pq[i] = pq[j]; 162 pq[j] = swap; 163 } 164 165 // is pq[1..N] a max heap? 166 private boolean isMaxHeap() { 167 return isMaxHeap(1); 168 } 169 170 // is subtree of pq[1..N] rooted at k a max heap? 171 private boolean isMaxHeap(int k) { 172 if (k > N) return true; 173 int left = 2*k, right = 2*k + 1; 174 if (left <= N && less(k, left)) return false; 175 if (right <= N && less(k, right)) return false; 176 return isMaxHeap(left) && isMaxHeap(right); 177 } 178 179 180 /* ********************************************************************* 181 * Iterator 182 **********************************************************************/ 183 184 /** 185 * Return an iterator that iterates over all of the keys on the priority queue 186 * in descending order. 187 * <p> 188 * The iterator doesn't implement {@code remove()} since it's optional. 189 */ 190 public Iterator<K> iterator() { return new HeapIterator(); } 191 192 private class HeapIterator implements Iterator<K> { 193 // create a new pq 194 private MaxPQ<K> copy; 195 196 // add all items to copy of heap 197 // takes linear time since already in heap order so no keys move 198 public HeapIterator() { 199 if (comparator == null) copy = new MaxPQ<K>(size()); 200 else copy = new MaxPQ<K>(size(), comparator); 201 for (int i = 1; i <= N; i++) 202 copy.insert(pq[i]); 203 } 204 205 public boolean hasNext() { return !copy.isEmpty(); } 206 public void remove() { throw new UnsupportedOperationException(); } 207 208 public K next() { 209 if (!hasNext()) throw new NoSuchElementException(); 210 return copy.delMax(); 211 } 212 } 213 214 void showHeap() { 215 for (int i = 1; i <= N; i++) 216 StdOut.print (pq[i] + " "); 217 StdOut.println (); 218 } 219 220 /** 221 * A test client. 222 */ 223 public static boolean DEBUG = false; 224 public static void main(String[] args) { 225 DEBUG = true; 226 MaxPQ<String> pq = new MaxPQ<>(100); 227 StdIn.fromString("10 20 30 40 50 - - - 05 25 35 - - - 70 80 05 - - - - "); 228 //StdIn.fromString("E A S Y Q U E S T I O N - - - - - - - - - - - -"); 229 while (!StdIn.isEmpty()) { 230 String item = StdIn.readString(); 231 if (item.equals("-")) StdOut.println("min: " + pq.delMax()); 232 else pq.insert(item); 233 StdOut.print ("pq: "); pq.showHeap(); 234 GraphvizBuilder.binaryHeapToFile (pq.pq, pq.N); 235 } 236 StdOut.println("(" + pq.size() + " left on pq)"); 237 } 238}