1 | // License: GPL v3 or later courtesy of author Kevin Wayne
|
---|
2 | package edu.princeton.cs.algs4;
|
---|
3 |
|
---|
4 | /*************************************************************************
|
---|
5 | * Compilation: javac IndexMinPQ.java
|
---|
6 | * Execution: java IndexMinPQ
|
---|
7 | *
|
---|
8 | * Indexed PQ implementation using a binary heap.
|
---|
9 | *
|
---|
10 | *********************************************************************/
|
---|
11 |
|
---|
12 | import java.util.Iterator;
|
---|
13 | import java.util.NoSuchElementException;
|
---|
14 |
|
---|
15 | public class IndexMinPQ<Key extends Comparable<Key>> implements Iterable<Integer> {
|
---|
16 | private int N; // number of elements on PQ
|
---|
17 | private int[] pq; // binary heap using 1-based indexing
|
---|
18 | private int[] qp; // inverse of pq - qp[pq[i]] = pq[qp[i]] = i
|
---|
19 | private Key[] keys; // keys[i] = priority of i
|
---|
20 |
|
---|
21 | public IndexMinPQ(int NMAX) {
|
---|
22 | keys = (Key[]) new Comparable[NMAX + 1]; // make this of length NMAX??
|
---|
23 | pq = new int[NMAX + 1];
|
---|
24 | qp = new int[NMAX + 1]; // make this of length NMAX??
|
---|
25 | for (int i = 0; i <= NMAX; i++) qp[i] = -1;
|
---|
26 | }
|
---|
27 |
|
---|
28 | // is the priority queue empty?
|
---|
29 | public boolean isEmpty() { return N == 0; }
|
---|
30 |
|
---|
31 | // is k an index on the priority queue?
|
---|
32 | public boolean contains(int k) {
|
---|
33 | return qp[k] != -1;
|
---|
34 | }
|
---|
35 |
|
---|
36 | // number of keys in the priority queue
|
---|
37 | public int size() {
|
---|
38 | return N;
|
---|
39 | }
|
---|
40 |
|
---|
41 | // associate key with index k
|
---|
42 | public void insert(int k, Key key) {
|
---|
43 | if (contains(k)) throw new NoSuchElementException("item is already in pq");
|
---|
44 | N++;
|
---|
45 | qp[k] = N;
|
---|
46 | pq[N] = k;
|
---|
47 | keys[k] = key;
|
---|
48 | swim(N);
|
---|
49 | }
|
---|
50 |
|
---|
51 | // return the index associated with a minimal key
|
---|
52 | public int minIndex() {
|
---|
53 | if (N == 0) throw new NoSuchElementException("Priority queue underflow");
|
---|
54 | return pq[1];
|
---|
55 | }
|
---|
56 |
|
---|
57 | // return a minimal key
|
---|
58 | public Key minKey() {
|
---|
59 | if (N == 0) throw new NoSuchElementException("Priority queue underflow");
|
---|
60 | return keys[pq[1]];
|
---|
61 | }
|
---|
62 |
|
---|
63 | // delete a minimal key and returns its associated index
|
---|
64 | public int delMin() {
|
---|
65 | if (N == 0) throw new NoSuchElementException("Priority queue underflow");
|
---|
66 | int min = pq[1];
|
---|
67 | exch(1, N--);
|
---|
68 | sink(1);
|
---|
69 | qp[min] = -1; // delete
|
---|
70 | keys[pq[N+1]] = null; // to help with garbage collection
|
---|
71 | pq[N+1] = -1; // not needed
|
---|
72 | return min;
|
---|
73 | }
|
---|
74 |
|
---|
75 | // return key associated with index k
|
---|
76 | public Key keyOf(int k) {
|
---|
77 | if (!contains(k)) throw new NoSuchElementException("item is not in pq");
|
---|
78 | else return keys[k];
|
---|
79 | }
|
---|
80 |
|
---|
81 | // change the key associated with index k
|
---|
82 | public void change(int k, Key key) {
|
---|
83 | changeKey(k, key);
|
---|
84 | }
|
---|
85 |
|
---|
86 | // change the key associated with index k
|
---|
87 | public void changeKey(int k, Key key) {
|
---|
88 | if (!contains(k)) throw new NoSuchElementException("item is not in pq");
|
---|
89 | keys[k] = key;
|
---|
90 | swim(qp[k]);
|
---|
91 | sink(qp[k]);
|
---|
92 | }
|
---|
93 |
|
---|
94 | // decrease the key associated with index k
|
---|
95 | public void decreaseKey(int k, Key key) {
|
---|
96 | if (!contains(k)) throw new NoSuchElementException("item is not in pq");
|
---|
97 | if (keys[k].compareTo(key) <= 0) throw new RuntimeException("illegal decrease");
|
---|
98 | keys[k] = key;
|
---|
99 | swim(qp[k]);
|
---|
100 | }
|
---|
101 |
|
---|
102 | // increase the key associated with index k
|
---|
103 | public void increaseKey(int k, Key key) {
|
---|
104 | if (!contains(k)) throw new NoSuchElementException("item is not in pq");
|
---|
105 | if (keys[k].compareTo(key) >= 0) throw new RuntimeException("illegal decrease");
|
---|
106 | keys[k] = key;
|
---|
107 | sink(qp[k]);
|
---|
108 | }
|
---|
109 |
|
---|
110 | // delete the key associated with index k
|
---|
111 | public void delete(int k) {
|
---|
112 | if (!contains(k)) throw new NoSuchElementException("item is not in pq");
|
---|
113 | int index = qp[k];
|
---|
114 | exch(index, N--);
|
---|
115 | swim(index);
|
---|
116 | sink(index);
|
---|
117 | keys[k] = null;
|
---|
118 | qp[k] = -1;
|
---|
119 | }
|
---|
120 |
|
---|
121 |
|
---|
122 | /**************************************************************
|
---|
123 | * General helper functions
|
---|
124 | **************************************************************/
|
---|
125 | private boolean greater(int i, int j) {
|
---|
126 | return keys[pq[i]].compareTo(keys[pq[j]]) > 0;
|
---|
127 | }
|
---|
128 |
|
---|
129 | private void exch(int i, int j) {
|
---|
130 | int swap = pq[i]; pq[i] = pq[j]; pq[j] = swap;
|
---|
131 | qp[pq[i]] = i; qp[pq[j]] = j;
|
---|
132 | }
|
---|
133 |
|
---|
134 |
|
---|
135 | /**************************************************************
|
---|
136 | * Heap helper functions
|
---|
137 | **************************************************************/
|
---|
138 | private void swim(int k) {
|
---|
139 | while (k > 1 && greater(k/2, k)) {
|
---|
140 | exch(k, k/2);
|
---|
141 | k = k/2;
|
---|
142 | }
|
---|
143 | }
|
---|
144 |
|
---|
145 | private void sink(int k) {
|
---|
146 | while (2*k <= N) {
|
---|
147 | int j = 2*k;
|
---|
148 | if (j < N && greater(j, j+1)) j++;
|
---|
149 | if (!greater(k, j)) break;
|
---|
150 | exch(k, j);
|
---|
151 | k = j;
|
---|
152 | }
|
---|
153 | }
|
---|
154 |
|
---|
155 |
|
---|
156 | /***********************************************************************
|
---|
157 | * Iterators
|
---|
158 | **********************************************************************/
|
---|
159 |
|
---|
160 | /**
|
---|
161 | * Return an iterator that iterates over all of the elements on the
|
---|
162 | * priority queue in ascending order.
|
---|
163 | * <p>
|
---|
164 | * The iterator doesn't implement <tt>remove()</tt> since it's optional.
|
---|
165 | */
|
---|
166 | public Iterator<Integer> iterator() { return new HeapIterator(); }
|
---|
167 |
|
---|
168 | private class HeapIterator implements Iterator<Integer> {
|
---|
169 | // create a new pq
|
---|
170 | private IndexMinPQ<Key> copy;
|
---|
171 |
|
---|
172 | // add all elements to copy of heap
|
---|
173 | // takes linear time since already in heap order so no keys move
|
---|
174 | public HeapIterator() {
|
---|
175 | copy = new IndexMinPQ<Key>(pq.length - 1);
|
---|
176 | for (int i = 1; i <= N; i++)
|
---|
177 | copy.insert(pq[i], keys[pq[i]]);
|
---|
178 | }
|
---|
179 |
|
---|
180 | public boolean hasNext() { return !copy.isEmpty(); }
|
---|
181 | public void remove() { throw new UnsupportedOperationException(); }
|
---|
182 |
|
---|
183 | public Integer next() {
|
---|
184 | if (!hasNext()) throw new NoSuchElementException();
|
---|
185 | return copy.delMin();
|
---|
186 | }
|
---|
187 | }
|
---|
188 |
|
---|
189 |
|
---|
190 | // public static void main(String[] args) {
|
---|
191 | // // insert a bunch of strings
|
---|
192 | // String[] strings = { "it", "was", "the", "best", "of", "times", "it", "was", "the", "worst" };
|
---|
193 | //
|
---|
194 | // IndexMinPQ<String> pq = new IndexMinPQ<String>(strings.length);
|
---|
195 | // for (int i = 0; i < strings.length; i++) {
|
---|
196 | // pq.insert(i, strings[i]);
|
---|
197 | // }
|
---|
198 | //
|
---|
199 | // // delete and print each key
|
---|
200 | // while (!pq.isEmpty()) {
|
---|
201 | // int i = pq.delMin();
|
---|
202 | // StdOut.println(i + " " + strings[i]);
|
---|
203 | // }
|
---|
204 | // StdOut.println();
|
---|
205 | //
|
---|
206 | // // reinsert the same strings
|
---|
207 | // for (int i = 0; i < strings.length; i++) {
|
---|
208 | // pq.insert(i, strings[i]);
|
---|
209 | // }
|
---|
210 | //
|
---|
211 | // // print each key using the iterator
|
---|
212 | // for (int i : pq) {
|
---|
213 | // StdOut.println(i + " " + strings[i]);
|
---|
214 | // }
|
---|
215 | // while (!pq.isEmpty()) {
|
---|
216 | // pq.delMin();
|
---|
217 | // }
|
---|
218 | //
|
---|
219 | // }
|
---|
220 | }
|
---|