001package algs24; 002import stdlib.*; 003 004/* *********************************************************************** 005 * Compilation: javac IndexMinPQ.java 006 * Execution: java IndexMinPQ 007 * 008 * Minimum-oriented indexed PQ implementation using a binary heap. 009 * 010 *********************************************************************/ 011 012import java.util.Iterator; 013import java.util.NoSuchElementException; 014 015/** 016 * The {@code IndexMinPQ} class represents an indexed priority queue of generic keys. 017 * It supports the usual <em>insert</em> and <em>delete-the-minimum</em> 018 * operations, along with <em>delete</em> and <em>change-the-key</em> 019 * methods. In order to let the client refer to items on the priority queue, 020 * an integer between 0 and NMAX-1 is associated with each key—the client 021 * uses this integer to specify which key to delete or change. 022 * It also supports methods for peeking at the minimum key, 023 * testing if the priority queue is empty, and iterating through 024 * the keys. 025 * <p> 026 * The <em>insert</em>, <em>delete-the-minimum</em>, <em>delete</em>, 027 * <em>change-key</em>, <em>decrease-key</em>, and <em>increase-key</em> 028 * operations take logarithmic time. 029 * The <em>is-empty</em>, <em>size</em>, <em>min-index</em>, <em>min-key</em>, and <em>key-of</em> 030 * operations take constant time. 031 * Construction takes time proportional to the specified capacity. 032 * <p> 033 * This implementation uses a binary heap along with an array to associate 034 * keys with integers in the given range. 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 IndexMinPQ<K extends Comparable<? super K>> implements Iterable<Integer> { 040 private int NMAX; // maximum number of elements on PQ 041 private int N; // number of elements on PQ 042 private int[] pq; // binary heap using 1-based indexing 043 private int[] qp; // inverse of pq - qp[pq[i]] = pq[qp[i]] = i 044 private K[] keys; // keys[i] = priority of i 045 046 /** 047 * Create an empty indexed priority queue with indices between {@code 0} and {@code NMAX-1}. 048 * @throws java.lang.IllegalArgumentException if {@code NMAX < 0} 049 */ 050 @SuppressWarnings("unchecked") 051 public IndexMinPQ(int NMAX) { 052 if (NMAX < 0) throw new IllegalArgumentException(); 053 this.NMAX = NMAX; 054 keys = (K[]) new Comparable[NMAX + 1]; // make this of length NMAX?? 055 pq = new int[NMAX + 1]; 056 qp = new int[NMAX + 1]; // make this of length NMAX?? 057 for (int i = 0; i <= NMAX; i++) qp[i] = -1; 058 } 059 060 /** 061 * Is the priority queue empty? 062 */ 063 public boolean isEmpty() { return N == 0; } 064 065 /** 066 * Is i an index on the priority queue? 067 * @throws java.lang.IndexOutOfBoundsException unless ({@code 0 <= i < NMAX}) 068 */ 069 public boolean contains(int i) { 070 if (i < 0 || i >= NMAX) throw new IndexOutOfBoundsException(); 071 return qp[i] != -1; 072 } 073 074 /** 075 * Return the number of keys on the priority queue. 076 */ 077 public int size() { 078 return N; 079 } 080 081 /** 082 * Associate key with index i. 083 * @throws java.lang.IndexOutOfBoundsException unless {@code 0 <= i < NMAX} 084 * @throws java.lang.IllegalArgumentException if there already is an item associated with index i. 085 */ 086 public void insert(int i, K key) { 087 if (i < 0 || i >= NMAX) throw new IndexOutOfBoundsException(); 088 if (contains(i)) throw new IllegalArgumentException("index is already in the priority queue"); 089 N++; 090 qp[i] = N; 091 pq[N] = i; 092 keys[i] = key; 093 swim(N); 094 } 095 096 /** 097 * Return the index associated with a minimal key. 098 * @throws java.util.NoSuchElementException if priority queue is empty. 099 */ 100 public int minIndex() { 101 if (N == 0) throw new NoSuchElementException("Priority queue underflow"); 102 return pq[1]; 103 } 104 105 /** 106 * Return a minimal key. 107 * @throws java.util.NoSuchElementException if priority queue is empty. 108 */ 109 public K minKey() { 110 if (N == 0) throw new NoSuchElementException("Priority queue underflow"); 111 return keys[pq[1]]; 112 } 113 114 /** 115 * Delete a minimal key and return its associated index. 116 * @throws java.util.NoSuchElementException if priority queue is empty. 117 */ 118 public int delMin() { 119 if (N == 0) throw new NoSuchElementException("Priority queue underflow"); 120 int min = pq[1]; 121 exch(1, N--); 122 sink(1); 123 qp[min] = -1; // delete 124 keys[pq[N+1]] = null; // to help with garbage collection 125 pq[N+1] = -1; // not needed 126 return min; 127 } 128 129 /** 130 * Return the key associated with index i. 131 * @throws java.lang.IndexOutOfBoundsException unless {@code 0 <= i < NMAX} 132 * @throws java.util.NoSuchElementException no key is associated with index i 133 */ 134 public K keyOf(int i) { 135 if (i < 0 || i >= NMAX) throw new IndexOutOfBoundsException(); 136 if (!contains(i)) throw new NoSuchElementException("index is not in the priority queue"); 137 else return keys[i]; 138 } 139 140 /** 141 * Change the key associated with index i to the specified value. 142 * @throws java.lang.IndexOutOfBoundsException unless {@code 0 <= i < NMAX} 143 * @deprecated Replaced by changeKey() 144 */ 145 @Deprecated public void change(int i, K key) { 146 changeKey(i, key); 147 } 148 149 /** 150 * Change the key associated with index i to the specified value. 151 * @throws java.lang.IndexOutOfBoundsException unless {@code 0 <= i < NMAX} 152 * @throws java.util.NoSuchElementException no key is associated with index i 153 */ 154 public void changeKey(int i, K key) { 155 if (i < 0 || i >= NMAX) throw new IndexOutOfBoundsException(); 156 if (!contains(i)) throw new NoSuchElementException("index is not in the priority queue"); 157 keys[i] = key; 158 swim(qp[i]); 159 sink(qp[i]); 160 } 161 162 /** 163 * Decrease the key associated with index i to the specified value. 164 * @throws java.lang.IndexOutOfBoundsException unless {@code 0 <= i < NMAX} 165 * @throws java.lang.IllegalArgumentException if key ≥ key associated with index i 166 * @throws java.util.NoSuchElementException no key is associated with index i 167 */ 168 public void decreaseKey(int i, K key) { 169 if (i < 0 || i >= NMAX) throw new IndexOutOfBoundsException(); 170 if (!contains(i)) throw new NoSuchElementException("index is not in the priority queue"); 171 if (keys[i].compareTo(key) <= 0) throw new IllegalArgumentException("Calling decreaseKey() with given argument would not strictly decrease the key"); 172 keys[i] = key; 173 swim(qp[i]); 174 } 175 176 /** 177 * Increase the key associated with index i to the specified value. 178 * @throws java.lang.IndexOutOfBoundsException unless {@code 0 <= i < NMAX} 179 * @throws java.lang.IllegalArgumentException if key ≤ key associated with index i 180 * @throws java.util.NoSuchElementException no key is associated with index i 181 */ 182 public void increaseKey(int i, K key) { 183 if (i < 0 || i >= NMAX) throw new IndexOutOfBoundsException(); 184 if (!contains(i)) throw new NoSuchElementException("index is not in the priority queue"); 185 if (keys[i].compareTo(key) >= 0) throw new IllegalArgumentException("Calling increaseKey() with given argument would not strictly increase the key"); 186 keys[i] = key; 187 sink(qp[i]); 188 } 189 190 /** 191 * Delete the key associated with index i. 192 * @throws java.lang.IndexOutOfBoundsException unless {@code 0 <= i < NMAX} 193 * @throws java.util.NoSuchElementException no key is associated with index i 194 */ 195 public void delete(int i) { 196 if (i < 0 || i >= NMAX) throw new IndexOutOfBoundsException(); 197 if (!contains(i)) throw new NoSuchElementException("index is not in the priority queue"); 198 int index = qp[i]; 199 exch(index, N--); 200 swim(index); 201 sink(index); 202 keys[i] = null; 203 qp[i] = -1; 204 } 205 206 207 /* ************************************************************ 208 * General helper functions 209 **************************************************************/ 210 private boolean greater(int i, int j) { 211 return keys[pq[i]].compareTo(keys[pq[j]]) > 0; 212 } 213 214 private void exch(int i, int j) { 215 int swap = pq[i]; pq[i] = pq[j]; pq[j] = swap; 216 qp[pq[i]] = i; qp[pq[j]] = j; 217 } 218 219 220 /* ************************************************************ 221 * Heap helper functions 222 **************************************************************/ 223 private void swim(int k) { 224 while (k > 1 && greater(k/2, k)) { 225 exch(k, k/2); 226 k = k/2; 227 } 228 } 229 230 private void sink(int k) { 231 while (2*k <= N) { 232 int j = 2*k; 233 if (j < N && greater(j, j+1)) j++; 234 if (!greater(k, j)) break; 235 exch(k, j); 236 k = j; 237 } 238 } 239 240 241 /* ********************************************************************* 242 * Iterators 243 **********************************************************************/ 244 245 /** 246 * Return an iterator that iterates over all of the elements on the 247 * priority queue in ascending order. 248 * <p> 249 * The iterator doesn't implement {@code remove()} since it's optional. 250 */ 251 public Iterator<Integer> iterator() { return new HeapIterator(); } 252 253 private class HeapIterator implements Iterator<Integer> { 254 // create a new pq 255 private IndexMinPQ<K> copy; 256 257 // add all elements to copy of heap 258 // takes linear time since already in heap order so no keys move 259 public HeapIterator() { 260 copy = new IndexMinPQ<>(pq.length - 1); 261 for (int i = 1; i <= N; i++) 262 copy.insert(pq[i], keys[pq[i]]); 263 } 264 265 public boolean hasNext() { return !copy.isEmpty(); } 266 public void remove() { throw new UnsupportedOperationException(); } 267 268 public Integer next() { 269 if (!hasNext()) throw new NoSuchElementException(); 270 return copy.delMin(); 271 } 272 } 273 274 275 public static void main(String[] args) { 276 // insert a bunch of strings 277 String[] strings = { "it", "was", "the", "best", "of", "times", "it", "was", "the", "worst" }; 278 279 IndexMinPQ<String> pq = new IndexMinPQ<>(strings.length); 280 for (int i = 0; i < strings.length; i++) { 281 pq.insert(i, strings[i]); 282 } 283 284 // delete and print each key 285 while (!pq.isEmpty()) { 286 int i = pq.delMin(); 287 StdOut.println(i + " " + strings[i]); 288 } 289 StdOut.println(); 290 291 // reinsert the same strings 292 for (int i = 0; i < strings.length; i++) { 293 pq.insert(i, strings[i]); 294 } 295 296 // print each key using the iterator 297 for (int i : pq) { 298 StdOut.println(i + " " + strings[i]); 299 } 300 while (!pq.isEmpty()) { 301 pq.delMin(); 302 } 303 304 } 305}