TopBlend:
Here is the
first difference.
There are 10 differences.
is old.
is new.
java.util
Class PriorityQueue<E>
java.lang.Object
java.util.AbstractCollection<E>
java.util.AbstractQueue<E>
java.util.PriorityQueue<E>
-
-
Type Parameters:
-
E - the type of elements held in this collection
-
All Implemented Interfaces:
-
Serializable
,
Iterable
<E>,
Collection
<E>,
Queue
<E>
-
public class PriorityQueue<E>
- extends AbstractQueue<E>
- implements Serializable
Queue<E>, Serializable
An unbounded priority
queue
based on a priority heap. This queue orders elements according to an order specified at construction time, which is specified either according to their
natural order
(see
Comparable
), or according to a
Comparator
, depending on which constructor is used. A priority queue does not permit
null
elements. A priority queue relying on natural ordering also does not permit insertion of non-comparable objects (doing so may result in
ClassCastException
).
The head of this queue is the least element with respect to the specified ordering. If multiple elements are tied for least value, the head is one of those elements -- ties are broken arbitrarily. The queue retrieval operations
poll
,
remove
,
peek
, and
element
access the element at the head of the queue.
A priority queue is unbounded, but has an internal
capacity
governing the size of an array used to store the elements on the queue. It is always at least as large as the queue size. As elements are added to a priority queue, its capacity grows automatically. The details of the growth policy are not specified.
This class
and its iterator implement
implements
all of the optional methods of the
Collection
and
Iterator
interfaces. The Iterator provided in method
iterator()
is not guaranteed to traverse the elements of the PriorityQueue in any particular order. If you need ordered traversal, consider using
Arrays.sort(pq.toArray())
.
Note that this implementation is not synchronized. Multiple threads should not access a
PriorityQueue
instance concurrently if any of the threads modifies the list structurally. Instead, use the thread-safe
PriorityBlockingQueue
class.
Implementation note: this implementation provides O(log(n)) time for the insertion methods (
offer
,
poll
,
remove()
and
add
) methods; linear time for the
remove(Object)
and
contains(Object)
methods; and constant time for the retrieval methods (
peek
,
element
, and
size
).
This class is a member of the
Java Collections Framework
.
-
Since:
-
1.5
-
See Also:
-
Serialized Form
Constructor Summary
|
PriorityQueue
()
Creates a
PriorityQueue
with the default initial capacity (11) that orders its elements according to their natural ordering (using
Comparable
). |
PriorityQueue
(
Collection
<? extends
E
> c)
Creates a
PriorityQueue
containing the elements in the specified collection. |
PriorityQueue
(int initialCapacity)
Creates a
PriorityQueue
with the specified initial capacity that orders its elements according to their natural ordering (using
Comparable
). |
PriorityQueue
(int initialCapacity,
Comparator
<? super
E
> comparator)
Creates a
PriorityQueue
with the specified initial capacity that orders its elements according to the specified comparator. |
PriorityQueue
(
PriorityQueue
<? extends
E
> c)
Creates a
PriorityQueue
containing the elements in the specified collection. |
PriorityQueue
(
SortedSet
<? extends
E
> c)
Creates a
PriorityQueue
containing the elements in the specified collection. |
Method Summary
|
boolean |
add
(
E
o)
Adds the specified element to this queue. |
void |
clear
()
Removes
Remove
all elements from the priority queue. |
Comparator
<? super
E
> |
comparator
()
Returns the comparator used to order this collection, or
null
if this collection is sorted according to its elements natural ordering (using
Comparable
). |
Iterator
<
E
> |
iterator
()
Returns an iterator over the elements in this queue. |
boolean |
offer
(
E
o)
Inserts the specified element into this priority queue. |
E
|
peek
()
Retrieves, but does not remove, the head of this queue, returning
null
if this queue is empty. |
E
|
poll
()
Retrieves and removes the head of this queue, or
null
if this queue is empty. |
boolean |
remove
(
Object
Removes a single instance of the specified element from this
queue,
collection,
if it is
present.
present (optional operation).
|
int |
size
()
Returns the number of elements in this collection. |
Methods inherited from class java.util.
AbstractQueue
|
addAll
,
element
,
remove
|
Methods inherited from class java.util.
AbstractCollection
|
contains
,
containsAll
,
isEmpty
,
removeAll
,
retainAll
,
toArray
,
toArray
,
toString
|
Methods inherited from class java.lang.
Object
|
clone
,
equals
,
finalize
,
getClass
,
hashCode
,
notify
,
notifyAll
,
wait
,
wait
,
wait
|
Methods inherited from interface java.util.
Queue
|
element
,
remove
|
PriorityQueue
public PriorityQueue()
-
Creates a
PriorityQueue
with the default initial capacity (11) that orders its elements according to their natural ordering (using
Comparable
).
PriorityQueue
public PriorityQueue(int initialCapacity)
-
Creates a
PriorityQueue
with the specified initial capacity that orders its elements according to their natural ordering (using
Comparable
).
-
Parameters:
-
initialCapacity - the initial capacity for this priority queue.
-
Throws:
-
IllegalArgumentException
- if
initialCapacity
is less than 1
PriorityQueue
public PriorityQueue(int initialCapacity,
Comparator<? super E> comparator)
-
Creates a
PriorityQueue
with the specified initial capacity that orders its elements according to the specified comparator.
-
Parameters:
-
initialCapacity - the initial capacity for this priority queue.
-
comparator - the comparator used to order this priority queue. If
null
then the order depends on the elements' natural ordering.
-
Throws:
-
IllegalArgumentException
- if
initialCapacity
is less than 1
PriorityQueue
public PriorityQueue(Collection<? extends E> c)
-
Creates a
PriorityQueue
containing the elements in the specified collection. The priority queue has an initial capacity of 110% of the size of the specified collection or 1 if the collection is empty. If the specified collection is an instance of a
SortedSet
or is another
PriorityQueue
, the priority queue will be sorted according to the same comparator, or according to its elements' natural order if the collection is sorted according to its elements' natural order. Otherwise, the priority queue is ordered according to its elements' natural order.
-
Parameters:
-
c - the collection whose elements are to be placed into this priority queue.
-
Throws:
-
ClassCastException
- if elements of the specified collection cannot be compared to one another according to the priority queue's ordering.
-
NullPointerException
- if
c
or any element within it is
null
PriorityQueue
public PriorityQueue(PriorityQueue<? extends E> c)
-
Creates a
PriorityQueue
containing the elements in the specified collection. The priority queue has an initial capacity of 110% of the size of the specified collection or 1 if the collection is empty. This priority queue will be sorted according to the same comparator as the given collection, or according to its elements' natural order if the collection is sorted according to its elements' natural order.
-
Parameters:
-
c - the collection whose elements are to be placed into this priority queue.
-
Throws:
-
ClassCastException
- if elements of the specified collection cannot be compared to one another according to the priority queue's ordering.
-
NullPointerException
- if
c
or any element within it is
null
PriorityQueue
public PriorityQueue(SortedSet<? extends E> c)
-
Creates a
PriorityQueue
containing the elements in the specified collection. The priority queue has an initial capacity of 110% of the size of the specified collection or 1 if the collection is empty. This priority queue will be sorted according to the same comparator as the given collection, or according to its elements' natural order if the collection is sorted according to its elements' natural order.
-
Parameters:
-
c - the collection whose elements are to be placed into this priority queue.
-
Throws:
-
ClassCastException
- if elements of the specified collection cannot be compared to one another according to the priority queue's ordering.
-
NullPointerException
- if
c
or any element within it is
null
offer
public boolean offer(E o)
-
Inserts the specified element into this priority queue.
-
-
Specified by:
-
offer
in interface
Queue
<
E
>
-
-
Parameters:
-
o - the element to insert.
-
Returns:
-
true
-
Throws:
-
ClassCastException
- if the specified element cannot be compared with elements currently in the priority queue according to the priority queue's ordering.
-
NullPointerException
- if the specified element is
null
.
peek
public E peek()
-
Description copied from interface:
Queue
-
Retrieves, but does not remove, the head of this queue, returning
null
if this queue is empty.
-
-
Specified by:
-
peek
in interface
Queue
<
E
>
-
-
Returns:
-
the head of this queue, or
null
if this queue is empty.
add
public boolean add(E o)
-
Adds the specified element to this queue.
-
-
Specified by:
-
add
in interface
Collection
<
E
>
-
Overrides:
-
add
in class
AbstractQueue
<
E
>
-
-
Parameters:
-
o - the element
-
Returns:
-
true
(as per the general contract of
Collection.add
).
-
Throws:
-
NullPointerException
- if the specified element is
null
.
-
ClassCastException
- if the specified element cannot be compared with elements currently in the priority queue according to the priority queue's ordering.
remove
public boolean remove(Object o)
-
Removes a single instance of the specified element from this queue, if it is present.
Description copied from class:
AbstractCollection
-
Removes a single instance of the specified element from this collection, if it is present (optional operation). More formally, removes an element
e
such that
(o==null ? e==null : o.equals(e))
, if the collection contains one or more such elements. Returns
true
if the collection contained the specified element (or equivalently, if the collection changed as a result of the call).
This implementation iterates over the collection looking for the specified element. If it finds the element, it removes the element from the collection using the iterator's remove method.
Note that this implementation throws an
UnsupportedOperationException
if the iterator returned by this collection's iterator method does not implement the
remove
method and this collection contains the specified object.
-
-
Specified by:
-
remove
in interface
Collection
<
E
>
-
Overrides:
-
remove
in class
AbstractCollection
<
E
>
-
-
Parameters:
-
o - element to be removed from this collection, if present.
-
Returns:
-
true
if the collection contained the specified element.
iterator
public Iterator<E> iterator()
-
Returns an iterator over the elements in this queue. The iterator does not return the elements in any particular order.
-
-
Specified by:
-
iterator
in interface
Iterable
<
E
>
-
Specified by:
-
iterator
in interface
Collection
<
E
>
-
Specified by:
-
iterator
in class
AbstractCollection
<
E
>
-
-
Returns:
-
an iterator over the elements in this queue.
size
public int size()
-
Description copied from class:
AbstractCollection
-
Returns the number of elements in this collection. If the collection contains more than
Integer.MAX_VALUE
elements, returns
Integer.MAX_VALUE
.
-
-
Specified by:
-
size
in interface
Collection
<
E
>
-
Specified by:
-
size
in class
AbstractCollection
<
E
>
-
-
Returns:
-
the number of elements in this collection.
clear
public void clear()
-
Removes
Remove
all elements from the priority queue.
The queue will be empty after this call returns.
-
-
Specified by:
-
clear
in interface
Collection
<
E
>
-
Overrides:
-
clear
in class
AbstractQueue
<
E
>
-
poll
public E poll()
-
Description copied from interface:
Queue
-
Retrieves and removes the head of this queue, or
null
if this queue is empty.
-
-
Specified by:
-
poll
in interface
Queue
<
E
>
-
-
Returns:
-
the head of this queue, or
null
if this queue is empty.
comparator
public Comparator<? super E> comparator()
-
Returns the comparator used to order this collection, or
null
if this collection is sorted according to its elements natural ordering (using
Comparable
).
-
-
-
Returns:
-
the comparator used to order this collection, or
null
if this collection is sorted according to its elements natural ordering.