---
description: Lazy and eager priority queues.
---

# 2.1. Simple 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`](https://github.com/emory-courses/dsa-java/blob/master/src/main/java/edu/emory/cs/queue/AbstractPriorityQueue.java) that is an abstract class to be inherited by all priority queues:

{% code lineNumbers="true" %}
```java
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;
    }
}
```
{% endcode %}

* `L1`: declares the [generic](https://docs.oracle.com/javase/tutorial/java/generics/) type `T` that is the type of input keys to be stored in this PQ.
  * `T` must be [comparable](https://docs.oracle.com/en/java/javase/14/docs/api/java.base/java/lang/Comparable.html) by its priority.
* `L2`: is a comparator that can compare keys of the generic type `T`.
  * `final`: must be initialized in every constructor.&#x20;
  * Comparators: [`naturalOrder()`](https://docs.oracle.com/en/java/javase/14/docs/api/java.base/java/util/Comparator.html#naturalOrder\(\)), [`reverseOrder()`](https://docs.oracle.com/en/java/javase/14/docs/api/java.base/java/util/Comparator.html#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`:

{% code lineNumbers="true" %}
```java
/**
 * 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();
```
{% endcode %}

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

{% code lineNumbers="true" %}
```java
/** @return true if this PQ is empty; otherwise, false. */
public boolean isEmpty() {
    return size() == 0;
}
```
{% endcode %}

## Lazy Priority Queue

Let us define [`LazyPriorityQueue`](https://github.com/emory-courses/dsa-java/blob/master/src/main/java/edu/emory/cs/queue/LazyPriorityQueue.java) 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.

{% code lineNumbers="true" %}
```java
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();
    }
}
```
{% endcode %}

* `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()`:

{% code lineNumbers="true" %}
```java
/**
 * 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;
}
```
{% endcode %}

* `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()`](https://docs.oracle.com/en/java/javase/14/docs/api/java.base/java/util/Collections.html#max\(java.util.Collection,java.util.Comparator\)) in $$O(n)$$.
  * `L18`: removes a key from the list in $$O(n+n) = O(n)$$.&#x20;

> 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`](https://github.com/emory-courses/dsa-java/blob/master/src/main/java/edu/emory/cs/queue/EagerPriorityQueue.java) 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?

{% code lineNumbers="true" %}
```java
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();
    }
}
```
{% endcode %}

* 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()`:

{% code lineNumbers="true" %}
```java
/**
 * 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);
}
```
{% endcode %}

* `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()`](https://docs.oracle.com/en/java/javase/14/docs/api/java.base/java/util/Collections.html#binarySearch\(java.util.List,T,java.util.Comparator\)) .
  * `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?
