static class Time {
long add = 0;
long remove = 0;
}L7: gets the snapshot of the ending time using currentTimeMillis().Supplier: passes a function as a parameter that returns a key of the generic type T.<T extends Comparable<T>> void addRuntime(AbstractPriorityQueue<T> queue, Time time, List<T> keys) {
long st, et;
// runtime for add()
st = System.currentTimeMillis();
keys.forEach(queue::add);
et = System.currentTimeMillis();
time.add += et - st;
// runtime for remove()
st = System.currentTimeMillis();
while (!queue.isEmpty()) queue.remove();
et = System.currentTimeMillis();
time.remove += et - st;
}<T extends Comparable<T>> Time[] benchmark(AbstractPriorityQueue<T>[] queues, int size, int iter, Supplier<T> sup) {
Time[] times = Stream.generate(Time::new).limit(queues.length).toArray(Time[]::new);
for (int i = 0; i < iter; i++) {
List<T> keys = Stream.generate(sup).limit(size).collect(Collectors.toList());
for (int j = 0; j < queues.length; j++)
addRuntime(queues[j], times[j], keys);
}
return times;
}@SafeVarargs
final void testRuntime(AbstractPriorityQueue<Integer>... queues) {
final int begin_size = 1000;
final int end_size = 10000;
final int inc = 1000;
final Random rand = new Random();
for (int size = begin_size; size <= end_size; size += inc) {
// JVM warm-up
benchmark(queues, size, 10, rand::nextInt);
// benchmark all priority queues with the same keys
Time[] times = benchmark(queues, size, 1000, rand::nextInt);
StringJoiner joiner = new StringJoiner("\t");
joiner.add(Integer.toString(size));
joiner.add(Arrays.stream(times).map(t -> Long.toString(t.add)).collect(Collectors.joining("\t")));
joiner.add(Arrays.stream(times).map(t -> Long.toString(t.remove)).collect(Collectors.joining("\t")));
System.out.println(joiner.toString());
}
}L8: compares the new key to its parent if exists.public class BinaryHeap<T extends Comparable<T>> extends AbstractPriorityQueue<T> {
private final List<T> keys;
public BinaryHeap() {
this(Comparator.naturalOrder());
}
public BinaryHeap(Comparator<T> priority) {
super(priority);
keys = new ArrayList<>();
keys.add(null);
}
@Override
public int size() {
return keys.size() - 1;
}
}/**
* @param i1 the index of the first key in {@link #keys}.
* @param i2 the index of the second key in {@link #keys}.
* @return a negative integer, zero, or a positive integer as the first key is
* less than, equal to, or greater than the second key.
*/
private int compare(int k1, int k2) {
return priority.compare(keys.get(k1), keys.get(k2));
}@Override
public void add(T key) {
keys.add(key);
swim(size());
}
private void swim(int k) {
for (; 1 < k && compare(k / 2, k) < 0; k /= 2)
Collections.swap(keys, k / 2, k);
}@Override
public T remove() {
if (isEmpty()) return null;
Collections.swap(keys, 1, size());
T max = keys.remove(size());
sink();
return max;
}
private void sink() {
for (int k = 1, i = 2; i <= size(); k = i, i *= 2) {
if (i < size() && compare(i, i + 1) < 0) i++;
if (compare(k, i) >= 0) break;
Collections.swap(keys, k, i);
}
}L2: is a comparator that can compare keys of the generic type T.L17-19: overrides the size() method.L16: edge case handling.L10: reverse engineers the return value of Collections.binarySearch() .public abstract class AbstractPriorityQueue<T extends Comparable<T>> {
protected final Comparator<T> priority;
/**
* Initializes this PQ as either a maximum or minimum PQ.
* @param priority if {@link Comparator#naturalOrder()}, this is a max PQ;
* if {@link Comparator#reverseOrder()}, this is a min PQ.
*/
public AbstractPriorityQueue(Comparator<T> priority) {
this.priority = priority;
}
}/**
* Adds a comparable key to this PQ.
* @param key the key to be added.
*/
abstract public void add(T key);
/**
* Removes the key with the highest/lowest priority if exists.
* @return the key with the highest/lowest priority if exists; otherwise, null.
*/
abstract public T remove();
/** @return the size of this PQ. */
abstract public int size();/** @return true if this PQ is empty; otherwise, false. */
public boolean isEmpty() {
return size() == 0;
}public class LazyPriorityQueue<T extends Comparable<T>> extends AbstractPriorityQueue<T> {
private final List<T> keys;
/** Initializes this as a maximum PQ. */
public LazyPriorityQueue() {
this(Comparator.naturalOrder());
}
/** @see AbstractPriorityQueue#AbstractPriorityQueue(Comparator). */
public LazyPriorityQueue(Comparator<T> priority) {
super(priority);
keys = new ArrayList<>();
}
@Override
public int size() {
return keys.size();
}
}/**
* Appends a key to {@link #keys}.
* @param key the key to be added.
*/
@Override
public void add(T key) {
keys.add(key);
}
/**
* Finds the key with the highest/lowest priority, and removes it from {@link #keys}.
* @return the key with the highest/lowest priority if exists; otherwise, null.
*/
@Override
public T remove() {
if (isEmpty()) return null;
T max = Collections.max(keys, priority);
keys.remove(max);
return max;
}public class EagerPriorityQueue<T extends Comparable<T>> extends AbstractPriorityQueue<T> {
private final List<T> keys;
public EagerPriorityQueue() {
this(Comparator.naturalOrder());
}
public EagerPriorityQueue(Comparator<T> priority) {
super(priority);
keys = new ArrayList<>();
}
@Override
public int size() {
return keys.size();
}
}/**
* Adds a key to {@link #keys} by the priority.
* @param key the key to be added.
*/
@Override
public void add(T key) {
// binary search (if not found, index < 0)
int index = Collections.binarySearch(keys, key, priority);
// if not found, the appropriate index is {@code -(index +1)}
if (index < 0) index = -(index + 1);
keys.add(index, key);
}
/**
* Remove the last key in the list.
* @return the key with the highest priority if exists; otherwise, {@code null}.
*/
@Override
public T remove() {
return isEmpty() ? null : keys.remove(keys.size() - 1);
}/**
* @param pq a priority queue.
* @param keys a list of comparable keys.
* @param comp a comparator used for sorting.
*/
<T extends Comparable<T>> void testRobustness(AbstractPriorityQueue<T> pq, List<T> keys, Comparator<T> comp) {
keys.forEach(pq::add);
keys = keys.stream().sorted(comp).collect(Collectors.toList());
keys.forEach(key -> assertEquals(key, pq.remove()));
}for (int i=0; i<keys.size(); i++)
pq.add(keys.get(i));for (T key : keys)
pq.add(key);keys.forEach(key -> pq.add(key));keys.forEach(pq::add);@Test
public void testRobustness() {
List<Integer> keys = List.of(4, 1, 3, 2, 5, 6, 8, 3, 4, 7, 5, 9, 7);
Comparator<Integer> natural = Comparator.naturalOrder();
Comparator<Integer> reverse = Comparator.reverseOrder();
testRobustness(new LazyPriorityQueue<>(), keys, reverse);
testRobustness(new EagerPriorityQueue<>(), keys, reverse);
testRobustness(new BinaryHeap<>(), keys, reverse);
testRobustness(new LazyPriorityQueue<>(reverse), keys, natural);
testRobustness(new EagerPriorityQueue<>(reverse), keys, natural);
testRobustness(new BinaryHeap<>(reverse), keys, natural);
}