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 typeT
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 typeT
.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()
: takesto add a key to the PQ.remove()
: takes 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
: declaresT
and passes it to its super class,AbstractPriorityQueue
.L2
: defines a list to store input keys.L17-19
: overrides thesize()
method.
Can you add keys to the member field
keys
when it is declared as final (a constant)? Why does all constructors inLazyPriorityQueue
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 .L15-20
: removes a key to the list in .L16
: edge case handling.L17
: finds the max-key in the list usingCollections.max()
in .L18
: removes a key from the list in .
Is
ArrayList
the best implementation ofList
forLazyPriorityQueue
? Why doesremove()
inL18
cost ?
Eager Priority Queues
Let us define EagerPriorityQueue
whose core methods satisfy the following conditions:
add()
: takesto add a key to the PQ.remove()
: takes 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 overEagerPQ
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 inLazyPriorityQueue
.
Should we create an abstract class that implements the above code and make it as a super class of
LazyPQ
andEagerPQ
? 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 .L8
: finds the index of the key to be inserted in the list using binary search in .L10
: reverse engineers the return value ofCollections.binarySearch()
.L11
: inserts the key at theindex
position in .
L19-21
: removes a key from the list in .
What are the worst-case complexities of
add()
andremove()
inLazyPQ
andEagerPQ
in terms of assignments and comparison?
Last updated
Was this helpful?