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