-
Notifications
You must be signed in to change notification settings - Fork 3
/
MinimumPriorityQueue.java
204 lines (161 loc) · 4.91 KB
/
MinimumPriorityQueue.java
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
package DataStructure;
import java.util.Comparator;
import java.util.Iterator;
import java.util.NoSuchElementException;
public class MinimumPriorityQueue<Key> implements Iterable<Key> {
private Key[] priorityQueue;
private int size;
private Comparator comparator;
/**
* Build a minimum priority queue, in which finding the
* minimum key and deleting it are O(1).
*
* @param capacity
*/
public MinimumPriorityQueue(int capacity) {
priorityQueue = (Key[]) new Object[capacity + 1];
size = 0;
}
/**
* Build a minimum priority queue, in which finding the
* minimum key and deleting it are O(1).
*/
public MinimumPriorityQueue() {
this(1);
}
/**
* Build a minimum priority queue, in which finding the
* minimum key and deleting it are O(1).
*
* @param capacity
* @param comparator
*/
public MinimumPriorityQueue(int capacity, Comparator comparator) {
priorityQueue = (Key[]) new Object[capacity + 1];
size = 0;
this.comparator = comparator;
}
/**
* Returns true if the priority queue is empty and
* false otherwise.
*/
public boolean isEmpty() {
return (size == 0);
}
/**
* Returns the size of the priority queue.
*/
public int size() {
return size;
}
/**
* Inserts the given key in the priority queue.
*
* @param key
*/
public void insert(Key key) {
if (size >= priorityQueue.length - 1) resize(priorityQueue.length * 2);
priorityQueue[++size] = key;
swim(size);
}
/**
* Deletes the minimum key and returns it.
*/
public Key deleteMin() throws NoSuchElementException {
if (isEmpty()) throw new NoSuchElementException("Empty priority queue.");
swap(1, size);
Key min = priorityQueue[size--];
sink(1);
priorityQueue[size + 1] = null;
if (size > 0 && (size == (priorityQueue.length - 1) / 4)) resize(priorityQueue.length / 2);
return min;
}
/**
* Returns the minimum key
*/
public Key min() throws NoSuchElementException {
if (isEmpty()) throw new NoSuchElementException("Empty priority queue.");
return priorityQueue[1];
}
/**
* Helper methods
*/
private void swim(int child) {
while (child > 1 && greater(child / 2, child)) {
swap(child, child / 2);
child = child / 2;
}
}
private void sink(int parent) {
while (2 * parent <= size) {
int child = 2 * parent;
if (child < size && greater(child, child + 1)) child++;
if (!greater(parent, child)) break;
swap(parent, child);
parent = child;
}
}
private void resize(int newSize) {
Key[] newPriorityQueue = (Key[]) new Object[newSize];
for (int i = 1; i <= size; i++) {
newPriorityQueue[i] = priorityQueue[i];
}
priorityQueue = newPriorityQueue;
}
// Helper functions for keys
private boolean greater(int rank1, int rank2) {
if (comparator != null) {
return comparator.compare(priorityQueue[rank1], priorityQueue[rank2]) > 0;
} else {
return ((Comparable<Key>) priorityQueue[rank1]).compareTo(priorityQueue[rank2]) > 0;
}
}
private void swap(int rank1, int rank2) {
Key key = priorityQueue[rank1];
priorityQueue[rank1] = priorityQueue[rank2];
priorityQueue[rank2] = key;
}
/**
* Returns an iterator over the keys in the priority queue,
* in increasing order.
*
* @return
*/
public Iterator<Key> iterator() {
return new HeapIterator();
}
private class HeapIterator implements Iterator<Key> {
private MinimumPriorityQueue<Key> copy;
public HeapIterator() {
if (comparator == null) copy = new MinimumPriorityQueue(size);
else copy = new MinimumPriorityQueue(size, comparator);
for (int i = 1; i <= size; i++) {
copy.insert(priorityQueue[i]);
}
}
public boolean hasNext() {
return !copy.isEmpty();
}
public void remove() {
throw new UnsupportedOperationException();
}
public Key next() {
if (!hasNext()) throw new NoSuchElementException();
return copy.deleteMin();
}
}
public static void main(String[] args) {
MinimumPriorityQueue minPQ = new MinimumPriorityQueue();
for (int i = 10; i > 0; i--) {
minPQ.insert(i);
}
for (int i = 10; i > 0; i--) {
System.out.println(minPQ.deleteMin());
}
try {
minPQ.deleteMin();
} catch (NoSuchElementException e) {
System.out.println("Passed exception test.");
}
}
}