public interface PriorityQueue<E>
extends java.util.Set<E>
add()
, changePriority()
,
removeFirst()
, and getFirst()
method calls.
There are several important differences between this interface and
the JDK PriorityQueue
:
double
values
as priorities for queue elements, while
java.util.PriorityQueue
uses either the elements'
natural order (see Comparable
) or a Comparator
.double
s represent higher
priorities; in java.util.PriorityQueue
, lesser
elements (with respect to the specified ordering) have higher
priorities.java.util.PriorityQueue
, that's not possible.BinaryHeapPriorityQueue
, is roughly 2x slower
than java.util.PriorityQueue
in informal benchmark
testing.BinaryHeapPriorityQueue
and nearly as
fast as PriorityQueue
, it does not support removing or
changing the priority of an element.
On the other hand, this interface and PriorityQueue
also have some characteristics in common:
Modifier and Type | Method and Description |
---|---|
boolean |
add(E key,
double priority)
Convenience method for if you want to pretend relaxPriority doesn't exist,
or if you really want to use the return conditions of add().
|
boolean |
changePriority(E key,
double priority)
Changes a priority, either up or down, adding the key it if it wasn't there already.
|
E |
getFirst()
Finds the object with the highest priority and returns it, without
modifying the queue.
|
double |
getPriority()
Gets the priority of the highest-priority element of the queue
(without modifying the queue).
|
double |
getPriority(E key)
Get the priority of a key.
|
boolean |
relaxPriority(E key,
double priority)
Increases the priority of the E key to the new priority if the old priority
was lower than the new priority.
|
E |
removeFirst()
Finds the object with the highest priority, removes it,
and returns it.
|
java.util.List<E> |
toSortedList() |
java.lang.String |
toString(int maxKeysToPrint)
Returns a representation of the queue in decreasing priority order,
displaying at most maxKeysToPrint elements.
|
E removeFirst()
E getFirst()
double getPriority()
double getPriority(E key)
key
- The object to assessboolean add(E key, double priority)
Warning: The semantics of this method currently varies between implementations. In some implementations, nothing will be changed if the key is already in the priority queue. In others, the element will be added a second time with the new priority. We maybe should at least change things so that the priority will be change to the priority given if the element is in the queue with a lower priority, but that wasn't the historical behavior, and it seemed like we'd need to do a lot of archeology before changing the behavior.
true
if this set did not already contain the specified
element.boolean changePriority(E key, double priority)
key
- an E
valueboolean relaxPriority(E key, double priority)
java.util.List<E> toSortedList()
java.lang.String toString(int maxKeysToPrint)
maxKeysToPrint
- The maximum number of keys to print. Less are
printed if there are less than this number of items in the
PriorityQueue. If this number is non-positive, then all elements in
the PriorityQueue are printed.