FibonacciMinPQ.java
9.1 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
/******************************************************************************
* Compilation: javac FibonacciMinPQ.java
* Execution:
*
* A Fibonacci heap.
*
******************************************************************************/
package edu.princeton.cs.algs4;
import java.util.Iterator;
import java.util.HashMap;
import java.util.NoSuchElementException;
import java.util.Comparator;
/*
* The FibonacciMinPQ class represents a priority queue of generic keys.
* It supports the usual insert and delete-the-minimum operations,
* along with the merging of two heaps together.
* It also supports methods for peeking at the minimum key,
* testing if the priority queue is empty, and iterating through
* the keys.
* It is possible to build the priority queue using a Comparator.
* If not, the natural order relation between the keys will be used.
*
* This implementation uses a Fibonacci heap.
* The delete-the-minimum operation takes amortized logarithmic time.
* The insert, min-key, is-empty, size, union and constructor take constant time.
*
* @author Tristan Claverie
*/
public class FibonacciMinPQ<Key> implements Iterable<Key> {
private Node head; //Head of the circular root list
private Node min; //Minimum Node of the root list
private int size; //Number of keys in the heap
private final Comparator<Key> comp; //Comparator over the keys
private HashMap<Integer, Node> table = new HashMap<Integer, Node>(); //Used for the consolidate operation
//Represents a Node of a tree
private class Node {
Key key; //Key of this Node
int order; //Order of the tree rooted by this Node
Node prev, next; //Siblings of this Node
Node child; //Child of this Node
}
/**
* Initializes an empty priority queue
* Worst case is O(1)
* @param C a Comparator over the Keys
*/
public FibonacciMinPQ(Comparator<Key> C) {
comp = C;
}
/**
* Initializes an empty priority queue
* Worst case is O(1)
*/
public FibonacciMinPQ() {
comp = new MyComparator();
}
/**
* Initializes a priority queue with given keys
* Worst case is O(n)
* @param a an array of keys
*/
public FibonacciMinPQ(Key[] a) {
comp = new MyComparator();
for (Key k : a) insert(k);
}
/**
* Initializes a priority queue with given keys
* Worst case is O(n)
* @param C a comparator over the keys
* @param a an array of keys
*/
public FibonacciMinPQ(Comparator<Key> C, Key[] a) {
comp = C;
for (Key k : a) insert(k);
}
/**
* Whether the priority queue is empty
* Worst case is O(1)
* @return true if the priority queue is empty, false if not
*/
public boolean isEmpty() {
return size == 0;
}
/**
* Number of elements currently on the priority queue
* Worst case is O(1)
* @return the number of elements on the priority queue
*/
public int size() {
return size;
}
/**
* Insert a key in the queue
* Worst case is O(1)
* @param key a Key
*/
public void insert(Key key) {
Node x = new Node();
x.key = key;
size++;
head = insert(x, head);
if (min == null) min = head;
else min = (greater(min.key, key)) ? head : min;
}
/**
* Gets the minimum key currently in the queue
* Worst case is O(1)
* @throws java.util.NoSuchElementException if the priority queue is empty
* @return the minimum key currently in the priority queue
*/
public Key minKey() {
if (isEmpty()) throw new NoSuchElementException("Priority queue is empty");
return min.key;
}
/**
* Deletes the minimum key
* Worst case is O(log(n)) (amortized)
* @throws java.util.NoSuchElementException if the priority queue is empty
* @return the minimum key
*/
public Key delMin() {
if (isEmpty()) throw new NoSuchElementException("Priority queue is empty");
head = cut(min, head);
Node x = min.child;
Key key = min.key;
min.key = null;
if (x != null) {
head = meld(head, x);
min.child = null;
}
size--;
if (!isEmpty()) consolidate();
else min = null;
return key;
}
/**
* Merges two heaps together
* This operation is destructive
* Worst case is O(1)
* @param that a Fibonacci heap
* @return the union of the two heaps
*/
public FibonacciMinPQ<Key> union(FibonacciMinPQ<Key> that) {
this.head = meld(head, that.head);
this.min = (greater(this.min.key, that.min.key)) ? that.min : this.min;
this.size = this.size+that.size;
return this;
}
/*************************************
* General helper functions
************************************/
//Compares two keys
private boolean greater(Key n, Key m) {
if (n == null) return false;
if (m == null) return true;
return comp.compare(n,m) > 0;
}
//Assuming root1 holds a greater key than root2, root2 becomes the new root
private void link(Node root1, Node root2) {
root2.child = insert(root1, root2.child);
root2.order++;
}
/*************************************
* Function for consolidating all trees in the root list
************************************/
//Coalesce the roots, thus reshapes the tree
private void consolidate() {
table.clear();
Node x = head;
int maxOrder = 0;
min = head;
Node y = null; Node z = null;
do {
y = x;
x = x.next;
z = table.get(y.order);
while (z != null) {
table.remove(y.order);
if (greater(y.key, z.key)) {
link(y, z);
y = z;
} else {
link(z, y);
}
z = table.get(y.order);
}
table.put(y.order, y);
if (y.order > maxOrder) maxOrder = y.order;
} while (x != head);
head = null;
for (Node n : table.values()) {
if (n != null) {
min = greater(min.key, n.key) ? n : min;
head = insert(n, head);
}
}
}
/*************************************
* General helper functions for manipulating circular lists
************************************/
//Inserts a Node in a circular list containing head, returns a new head
private Node insert(Node x, Node head) {
if (head == null) {
x.prev = x;
x.next = x;
} else {
head.prev.next = x;
x.next = head;
x.prev = head.prev;
head.prev = x;
}
return x;
}
//Removes a tree from the list defined by the head pointer
private Node cut(Node x, Node head) {
if (x.next == x) {
x.next = null;
x.prev = null;
return null;
} else {
x.next.prev = x.prev;
x.prev.next = x.next;
Node res = x.next;
x.next = null;
x.prev = null;
if (head == x) return res;
else return head;
}
}
//Merges two root lists together
private Node meld(Node x, Node y) {
if (x == null) return y;
if (y == null) return x;
x.prev.next = y.next;
y.next.prev = x.prev;
x.prev = y;
y.next = x;
return x;
}
/*************************************
* Iterator
************************************/
/**
* Gets an Iterator over the Keys in the priority queue in ascending order
* The Iterator does not implement the remove() method
* iterator() : Worst case is O(n)
* next() : Worst case is O(log(n)) (amortized)
* hasNext() : Worst case is O(1)
* @return an Iterator over the Keys in the priority queue in ascending order
*/
public Iterator<Key> iterator() {
return new MyIterator();
}
private class MyIterator implements Iterator<Key> {
private FibonacciMinPQ<Key> copy;
//Constructor takes linear time
public MyIterator() {
copy = new FibonacciMinPQ<Key>(comp);
insertAll(head);
}
private void insertAll(Node head) {
if (head == null) return;
Node x = head;
do {
copy.insert(x.key);
insertAll(x.child);
x = x.next;
} while (x != head);
}
public void remove() {
throw new UnsupportedOperationException();
}
public boolean hasNext() {
return !copy.isEmpty();
}
//Takes amortized logarithmic time
public Key next() {
if (!hasNext()) throw new NoSuchElementException();
return copy.delMin();
}
}
/*************************************
* Comparator
************************************/
//default Comparator
private class MyComparator implements Comparator<Key> {
@Override
public int compare(Key key1, Key key2) {
return ((Comparable<Key>) key1).compareTo(key2);
}
}
}
/******************************************************************************
* Copyright 2002-2016, Robert Sedgewick and Kevin Wayne.
*
* This file is part of algs4.jar, which accompanies the textbook
*
* Algorithms, 4th edition by Robert Sedgewick and Kevin Wayne,
* Addison-Wesley Professional, 2011, ISBN 0-321-57351-X.
* http://algs4.cs.princeton.edu
*
*
* algs4.jar is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* algs4.jar is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with algs4.jar. If not, see http://www.gnu.org/licenses.
******************************************************************************/