Time

Let us define a static nested class Time under PriorityQueueTest that stores runtimes for the add() and remove() methods in any PQ:

static class Time {
    long add = 0;
    long remove = 0;
}

What is the advantage of defining static nested class over non-static nested class?

Runtime Estimation

Let us define addRuntime() that estimates the runtime for add() and remove()for a particular PQ:

<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;
}

• L5-8: estimates the runtime for add():

  • L5: gets the snapshot of the starting time using currentTimeMillis().

  • L7: gets the snapshot of the ending time using currentTimeMillis().

  • L8: accumulates the runtime to times.add.

• L11-14: estimates the runtime for remove().

Is the approach using currentTimeMillis() a proper way of benchmarking the speed?

We then define benchmark() that estimates the speeds of multiple PQs using the same lists of keys by calling addRuntime():

<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;
}

• L1: method declaration:

  • AbstractPriorityQueue[]: It is unusual to declare an array of objects involving generics in Java (you will see the unique use case of it in the testSpeedAux() method).

  • Supplier: passes a function as a parameter that returns a key of the generic type T.

• L2: generates an array of Time using several stream operations. The dimension of times[] is the same as the dimension of queues such that times[i] accumulates the speeds taken by the queue[i], respectively.

  • generate(): creates a stream specified by the supplier.

  • limit(): creates a stream with a specific size.

  • toArray(): returns an array of the specific type.

• L4: benchmarks the PQs multiple times as specified by iter.

• L5: generates the list of keys specified by the supplier sup.

• L6-7: estimate the runtimes by using the same list of keys for each PQ.

Why do we need to benchmark the priority queues multiple times?

Benchmark

Let us define testSpeedAux() that takes multiple PQs and prints out the benchmarking results:

@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());
    }
}

• L1: annotates safeVarargs indicating that this method takes vararg parameters.

• L2: declares a final method that cannot be overridden by its subclasses.

  • It can take a 0-to-many number of abstract PQs.

  • The type of queues is AbstractPriorityQueue<Integer>[] such that it can be directly passed to the benchmark() method.

• L5: creates a random generator.

• L8: benchmarks different sizes of PQs.

• L10: warms up the Java Virtual Machine (JVM) before the actual benchmarking.

  • rand::nextnt that is equivalent to the lambda expression of () -> rand.nextInt().

• L12: benchmarks add() and remove() in the PQs.

• L14-18: prints the benchmark results.

  • L14: uses StringJoiner to concatenate strings with the specific delimiter.

  • L16: exercise.

Why is it recommended to declare the method final if it takes vararg parameters? Why does JVM need to be warmed-up before the actual benchmarking? Why should you use StringJoiner instead of concatenating strings with the + operator?

Speed Comparison

The followings show runtime comparisons between LazyPQ, EagerPQ, and BinaryHeap:

Contents

1. Simple Priority Queues

2. Binary Heap

3. Unit Testing

4. Benchmarking

5. Quiz

Resources

• Main: src/main/java/edu/emory/cs/queue

• Test: test/java/edu/emory/cs/queue

References

• Binary Heap

• Fibonacci Heap

A priority queue (PQ) is a data structure that supports the following two operations:

• add(): adds a comparable key to the PQ.

• remove(): removes the key with the highest (or lowest) priority in the PQ.

A PQ that removes the key with the highest priority is called a maximum PQ (max-PQ), and with the lowest priority is called a minimum PQ (min-PQ).

Does a priority queue need to be sorted at all time to support those two operations? What are the use cases of priority queues?

Abstract Priority Queue

Let us define AbstractPriorityQueue that is an abstract class to be inherited by all priority queues:

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;
    }
}

• L1: declares the generic type T that is the type of input keys to be stored in this PQ.

  • T must be comparable by its priority.

• L2: is a comparator that can compare keys of the generic type T.

  • final: must be initialized in every constructor.

  • Comparators: naturalOrder(), reverseOrder().

• L6: the javadoc {@link} hyperlinks to the specified methods.

What are comparable data types in Java? Can you define your own comparator?

Let us define three abstract methods, add(), remove(), and size() in AbstractPriorityQueue:

/**
 * 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();

Given the abstract methods, we can define the regular method isEmpty():

/** @return true if this PQ is empty; otherwise, false. */
public boolean isEmpty() {
    return size() == 0;
}

Lazy Priority Queue

Let us define LazyPriorityQueue whose core methods satisfy the following conditions:

In other words, all the hard work is done at the last minute when it needs to remove the key.

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();
    }
}

• L1: declares T and passes it to its super class, AbstractPriorityQueue.

• L2: defines a list to store input keys.

• L17-19: overrides the size() method.

Can you add keys to the member field keys when it is declared as final (a constant)? Why does all constructors in LazyPriorityQueue need to call the super constructor?

We then override the core methods, add() and remove():

/**
 * 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;
}

• • L16: edge case handling.

Eager Priority Queues

Let us define EagerPriorityQueue whose core methods satisfy the following conditions:

In other words, all the hard work is done as soon as a key is added.

What are the situations that LazyPQ is preferred over EagerPQ and vice versa?

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();
    }
}

• The implementations of the two constructors and the size() method are identical to the ones in LazyPriorityQueue.

Should we create an abstract class that implements the above code and make it as a super class of LazyPQ and EagerPQ? What level of abstraction is appropriate in object-oriented programming?

We then override the core methods, add() and remove():

/**
 * 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);
}

• • L10: reverse engineers the return value of Collections.binarySearch() .

What are the worst-case complexities of add() and remove() in LazyPQ and EagerPQ in terms of assignments and comparison?

A binary heap is a PQ that takes$O(\log n)$for both add() and remove(), where keys are stored in a balanced binary tree in which every node has a higher priority than its children (when used as a max-PQ).

When should we use a binary heap over a lazy PQ or an eager PQ?

Balanced Binary Tree

A balanced binary tree can be implemented by a list such that given the $k$'th key in the list:

• The index of its parent: $\lfloor \frac{k}{2} \rfloor$

• The index of its left child: $2 \cdot k$.

• The index of its right child: $2 \cdot k + 1$.

• e.g., given the list [1, 2, 3, 4, 5], 1 is the root, 2 and 3 are the left and right children of 1, and 4 and 5 are the left and right children of 2, respectively.

Is the tree represented by the list [1, 2, 3, 4, 5] balanced?

Implementation

Let us create the BinaryHeap class inheriting AbstractPriorityQueue:

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;
    }
}

• L11: adding null as the first item makes it easier to calculate the indices of parents and children.

• L16: keys has the extra item of null from L11 that is not an input key.

How does adding null make the calculation of the indices easier?

Additionally, let us define the helper method compare() that compares two keys in the list:

/**
 * @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));
}

• L8: calls the compare() method in the member field priority declared in the super class.

Add() with Swim

The add() method in a heap uses the operation called swim as follows:

@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);
}

• L3: appends the new key to the list.

• L7-10: keeps swimming until the list becomes a heap:

  • L8: compares the new key to its parent if exists.

  • L9: if the new key has a higher priority than its parent, Collections.swap() them.

How many keys are compared at most for the `add operation?

Remove() with Sink

The remove() method in a heap uses the operation called sink as follows:

@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);
    }
}

• L3: checks if the heap is empty.

• L4: swaps the root and the last key in the list.

• L3: removes the (swapped) last key with the highest priority in this heap.

• L10-16: keeps sinking until the list becomes a heap:

  • L12: finds the child with a higher priority.

  • L13: breaks if the parent has a higher priority than the child.

  • L14: swaps if the child has a higher priority than the parent.

How many keys are compared at most for the remove operation?

Coding

• Create a class called under the main package that extends the abstract class .

• Each node in TernaryHeapQuiz takes up to 3 children, so it becomes a ternary instead of a binary tree.

• Override the required abstract methods, , , and , such that both add() and remove() give .

• Feel free to use the code in .

Testing

• Create the class under the test package.

• Test the correctness of your TernaryHeapQuiz using the method.

• Add more tests for a more thorough assessment if necessary.

Benchmarking

• Compare runtime speeds between BinaryHeap and TernaryHeapQuiz for add() and remove() using the method.

• Create a PDF file quiz2.pdf and write a report that includes the following:

  • A table and a chart to compare speeds between the two priority queues for those two methods, add() and remove(), with respect to different input sizes.

  • A brief explanation of why a certain PQ is faster than the other PQ with respect to different input sizes.

Submission

1. Commit and push everything under the following packages to your GitHub repository:

2. Submit quiz2.pdf to Canvas.

Auxiliary Method

Let us create and define testRobustnessAux() that checks the robustness of any PQ inheriting AbstractPriorityQueue:

• L6: the generic type T is defined specifically for this method such that the priority queue pq, the list keys, and the comparator comp take the same type T that is comparable.

• L7: any collection that inherits the interface has the member method that takes a and applies each key in the collection to the consumer.

• L8: any collection has the member method that returns the of the collection.

  • : creates a stream of the collection whose keys are sorted

  • : creates a collection specified by the .

  • : returns a collector that transforms the stream into a list.

• L9: iterates each of the sorted keys and compares it to the returned value of pq.remove().

What are the advantages of defining a method-level generic type?

Functional Programming

The following code shows a traditional way of iterating over a list (that is equivalent to L7 above):

Java 5 introduced an enhanced for loop that simplified the traditional for loop:

The syntax of the above code can be simplified as follows (as shown in L7):

What are the main differences between object-oriented programming and functional programming?

Test: Robustness

Let us define the testRobustness() method that calls the auxiliary method testRobustnessAux():

• L7-9: tests different types of max-PQs. The keys need to be sorted in reverse order for it to test the remove() method.

• L11-13: tests different types of min-PQs. The keys need to be sorted in the natural order for it to test the remove() method.

The generic types of the PQs in L4-5 are explicitly coded as <Integer>, whereas they are simplified to <> in L7-13. When do generic types need to be explicitly coded?