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?
Let us define AbstractPriorityQueue
that is an abstract class to be inherited by all priority queues:
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
:
Given the abstract methods, we can define the regular method isEmpty()
:
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.
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 inLazyPriorityQueue
need to call the super constructor?
We then override the core methods, add()
and remove()
:
L16
: edge case handling.
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 overEagerPQ
and vice versa?
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
andEagerPQ
? What level of abstraction is appropriate in object-oriented programming?
We then override the core methods, add()
and remove()
:
L10
: reverse engineers the return value of Collections.binarySearch()
.
What are the worst-case complexities of
add()
andremove()
inLazyPQ
andEagerPQ
in terms of assignments and comparison?
add()
: takesto add a key to the PQ.
remove()
: takes to remove the key with the highest/lowest priority from the PQ.
L6-8
: appends a key to the list in .
L15-20
: removes a key to the list in .
L17
: finds the max-key in the list using Collections.max()
in .
L18
: removes a key from the list in .
Is ArrayList
the best implementation of List
for LazyPriorityQueue
?
Why does remove()
in L18
cost ?
add()
: takesto add a key to the PQ.
remove()
: takes to remove the key with the highest/lowest priority from the PQ.
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 .
L11
: inserts the key at the index
position in .
L19-21
: removes a key from the list in .