001package algs24; 002import stdlib.*; 003import java.util.Iterator; 004import java.util.NoSuchElementException; 005/* *********************************************************************** 006 * Compilation: javac MaxPQ.java 007 * Execution: java MaxPQ < input.txt 008 * 009 * Generic max priority queue implementation with a binary heap. 010 * 011 * % java MaxPQ < tinyPQ.txt 012 * Q X P (6 left on pq) 013 * 014 * We use a one-based array to simplify parent and child calculations. 015 * 016 *************************************************************************/ 017/* Modified by jriely@cs.depaul.edu */ 018public class XFixedMaxPQ<K extends Comparable<? super K>> implements Iterable<K> { 019 private final K[] pq; // store items at indices 1 to N 020 private int N; // number of items on priority queue 021 private final int MAXN; 022 023 @SuppressWarnings("unchecked") 024 /** Create an empty priority queue with the given initial capacity, using the given comparator. */ 025 public XFixedMaxPQ(int initCapacity) { 026 MAXN = initCapacity; 027 pq = (K[]) new Comparable[initCapacity + 1]; 028 N = 0; 029 } 030 031 /** Is the priority queue empty? */ 032 public boolean isEmpty() { return N == 0; } 033 034 /** Is the priority queue full? */ 035 public boolean isFull() { return N == MAXN; } 036 037 /** Return the number of items on the priority queue. */ 038 public int size() { return N; } 039 040 /** 041 * Return the largest key on the priority queue. 042 * Throw an exception if the priority queue is empty. 043 */ 044 public K max() { 045 if (isEmpty()) throw new Error("Priority queue underflow"); 046 return pq[1]; 047 } 048 049 /** Add a new key to the priority queue. */ 050 public void insert(K x) { 051 if (isFull()) throw new Error("Priority queue overflow"); 052 053 // add x, and percolate it up to maintain heap invariant 054 pq[++N] = x; 055 swim(N); 056 //assert isMaxHeap(); 057 } 058 059 /** 060 * Delete and return the largest key on the priority queue. 061 * Throw an exception if the priority queue is empty. 062 */ 063 public K delMax() { 064 if (N == 0) throw new Error("Priority queue underflow"); 065 K max = pq[1]; 066 exch(1, N--); 067 sink(1); 068 pq[N+1] = null; // avoid loitering and help with garbage collection 069 //assert isMaxHeap(); 070 return max; 071 } 072 073 074 /* ********************************************************************* 075 * Helper functions to restore the heap invariant. 076 **********************************************************************/ 077 078 private void swim(int k) { 079 while (k > 1 && less(k/2, k)) { 080 exch(k, k/2); 081 k = k/2; 082 } 083 } 084 085 private void sink(int k) { 086 while (2*k <= N) { 087 int j = 2*k; 088 if (j < N && less(j, j+1)) j++; 089 if (!less(k, j)) break; 090 exch(k, j); 091 k = j; 092 } 093 } 094 095 /* ********************************************************************* 096 * Helper functions for compares and swaps. 097 **********************************************************************/ 098 private boolean less(int i, int j) { 099 return pq[i].compareTo(pq[j]) < 0; 100 } 101 102 private void exch(int i, int j) { 103 K swap = pq[i]; 104 pq[i] = pq[j]; 105 pq[j] = swap; 106 } 107 108 // is pq[1..N] a max heap? 109 private boolean isMaxHeap() { 110 return isMaxHeap(1); 111 } 112 113 // is subtree of pq[1..N] rooted at k a max heap? 114 private boolean isMaxHeap(int k) { 115 if (k > N) return true; 116 int left = 2*k, right = 2*k + 1; 117 if (left <= N && less(k, left)) return false; 118 if (right <= N && less(k, right)) return false; 119 return isMaxHeap(left) && isMaxHeap(right); 120 } 121 122 123 /* ********************************************************************* 124 * Iterator 125 **********************************************************************/ 126 127 /** 128 * Return an iterator that iterates over all of the keys on the priority queue 129 * in descending order. 130 * <p> 131 * The iterator doesn't implement {@code remove()} since it's optional. 132 */ 133 public Iterator<K> iterator() { return new HeapIterator(); } 134 135 private class HeapIterator implements Iterator<K> { 136 // create a new pq 137 private final XFixedMaxPQ<K> copy; 138 139 // add all items to copy of heap 140 // takes linear time since already in heap order so no keys move 141 public HeapIterator() { 142 copy = new XFixedMaxPQ<>(size()); 143 for (int i = 1; i <= N; i++) 144 copy.insert(pq[i]); 145 } 146 147 public boolean hasNext() { return !copy.isEmpty(); } 148 public void remove() { throw new UnsupportedOperationException(); } 149 150 public K next() { 151 if (!hasNext()) throw new NoSuchElementException(); 152 return copy.delMax(); 153 } 154 } 155 156 private void showHeap() { 157 for (int i = 1; i <= N; i++) 158 StdOut.print (pq[i] + " "); 159 StdOut.println (); 160 } 161 162 /** 163 * A test client. 164 */ 165 public static void main(String[] args) { 166 XFixedMaxPQ<String> pq = new XFixedMaxPQ<>(100); 167 StdIn.fromString("10 20 30 40 50 - - - 05 25 35 - - - 70 80 05 - - - - "); 168 while (!StdIn.isEmpty()) { 169 StdOut.print ("pq: "); pq.showHeap(); 170 String item = StdIn.readString(); 171 if (item.equals("-")) StdOut.println("max: " + pq.delMax()); 172 else pq.insert(item); 173 } 174 StdOut.println("(" + pq.size() + " left on pq)"); 175 } 176 177}