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