2.1. Simple Priority Queues

Lazy and eager priority queues.

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:

• add(): takes$O(1)$to add a key to the PQ.
• remove(): takes$O(n)$ to remove the key with the highest/lowest priority from the PQ.

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

• L6-8: appends a key to the list in $O(1)$.
• L15-20: removes a key to the list in $O(n)$.

  • L16: edge case handling.

  • L17: finds the max-key in the list using Collections.max() in $O(n)$.
  • L18: removes a key from the list in $O(n+n) = O(n)$.

Is ArrayList the best implementation of List for LazyPriorityQueue? Why does remove() in L18 cost $O(n+n)$?

Eager Priority Queues

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

• add(): takes$O(n)$to add a key to the PQ.
• remove(): takes$O(1)$ to remove the key with the highest/lowest priority from the PQ.

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

• L6-12: inserts a key to the list in $O(n)$ .

  • L8: finds the index of the key to be inserted in the list using binary search in $O(\log n)$.
  • L10: reverse engineers the return value of Collections.binarySearch() .

  • L11: inserts the key at the index position in $O(n)$.
• L19-21: removes a key from the list in $O(1)$.

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