TopBlend:
Here is the
first difference.
There are 74 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
An unbounded priority
queue
based on a priority heap.
The elements of the priority queue are ordered according to their
natural ordering
This queue orders elements according to an order specified at construction time, which is specified either according to their
natural order
(see
Comparable
,
),
or
by
according to
a
Comparator
provided at queue construction time,
,
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 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
priority queue
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
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
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
Creates a
PriorityQueue
containing the elements in the specified
priority queue.
collection.
|
PriorityQueue
(
SortedSet
<? extends
E
Creates a
PriorityQueue
containing the elements in the specified
sorted set.
collection.
|
Method Summary
|
boolean |
add
(
E
Inserts
Adds
the specified element
into
to
this
priority
queue. |
void |
clear
()
Removes all
of the
elements from
this
the
priority queue. |
Comparator
<? super
E
|
comparator
()
Returns the comparator used to order
the elements in
this
queue,
collection,
or
null
if this
queue
collection
is sorted according to
the
natural ordering
its elements natural ordering (using
Comparable
).
|
boolean
|
contains
(
Object
Returns
true
if this queue contains the specified element.
|
Iterator
<
E
> |
iterator
()
Returns an iterator over the elements in this queue. |
boolean |
offer
(
E
Inserts the specified element into this priority queue. |
E
|
peek
()
Retrieves, but does not remove, the head of this queue,
or returns
returning
null
if this queue is empty. |
E
|
poll
()
Retrieves and removes the head of this queue, or
returns
null
if this queue is empty. |
boolean |
remove
(
Object
o)
Removes a single instance of the specified element from this queue, if it is present. |
int |
size
()
Returns the number of elements in this collection. |
PriorityQueue
public PriorityQueue()
-
Creates a
PriorityQueue
with the default initial capacity (11) that orders its elements according to their
natural ordering
.
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
.
natural ordering (using
Comparable
).
-
Parameters:
-
initialCapacity - the initial capacity for this priority
queue
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
queue.
-
comparator - the comparator
that will be
used to order this priority queue. If
null
, the
natural ordering
of the elements will be used.
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 ordered according to the same ordering. Otherwise, this priority queue will be ordered according to the natural ordering of its elements.
, 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
queue.
-
Throws:
-
ClassCastException
- if elements of the specified collection cannot be compared to one another according to the priority queue's
ordering
ordering.
-
NullPointerException
- if the specified collection or any of its elements are null
- 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
priority queue.
collection.
The priority queue has an initial capacity of 110% of the size of the specified
priority queue
collection
or 1 if the
priority queue
collection
is empty. This priority queue will be
ordered
sorted
according to the same
ordering
comparator
as the given
priority queue.
collection, or according to its elements' natural order if the collection is sorted according to its elements' natural order.
-
Parameters:
-
c - the
priority queue
collection
whose elements are to be placed into this priority
queue
queue.
-
Throws:
-
ClassCastException
- if elements of
- if elements of the specified collection cannot be compared to one another according to the priority queue's ordering.
-
NullPointerException
- if
c
cannot be compared to one another according to
or any element within it is
c
null
's ordering
-
NullPointerException
- if the specified priority queue or any of its elements are null
PriorityQueue
public PriorityQueue(SortedSet<? extends E> c)
-
Creates a
PriorityQueue
containing the elements in the specified
sorted set.
collection.
The priority queue has an initial capacity of 110% of the size of the specified
sorted set
collection
or 1 if the
sorted set
collection
is empty. This priority queue will be
ordered
sorted
according to the same
ordering
comparator
as the given
collection, or according to its elements' natural order if the collection is
sorted
set.
according to its elements' natural order.
-
Parameters:
-
c - the
sorted set
collection
whose elements are to be placed into this priority queue. -
Throws:
-
ClassCastException
- if elements of the specified
sorted set
collection
cannot be compared to one another according to the
sorted set's ordering
priority queue's ordering.
-
NullPointerException
- if the specified sorted set or any of its elements are null
- if
c
or any element within it is
null
add
public boolean
add
(
E
e)
-
Inserts the specified element into this priority queue.
-
-
Specified by:
-
add
in interface
Collection
<
E
>
-
Specified by:
-
add
in interface
Queue
<
E
>
-
Overrides:
-
add
in class
AbstractQueue
<
E
>
-
-
Parameters:
-
e - the element to add
-
Returns:
-
true
(as specified by
Collection.add(E)
)
-
Throws:
-
ClassCastException
- if the specified element cannot be compared with elements currently in this priority queue according to the priority queue's ordering
-
NullPointerException
- if the specified element is null
offer
public boolean offer(E
e) ![](../../diffpics/oold.gif)
o)
-
Inserts the specified element into this priority queue.
-
-
Specified by:
-
offer
in interface
Queue
<
E
>
-
-
Parameters:
-
e
o
- the element to
add
insert.
-
Returns:
-
true
(as specified by
Queue.offer(E)
)
-
Throws:
-
ClassCastException
- if the specified element cannot be compared with elements currently in
this
the
priority queue according to the priority queue's
ordering
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,
or returns
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
empty.
remove
add
public boolean
remove ![](../../diffpics/oold.gif)
add (
Object![](../../diffpics/oold.gif)
E o)
-
Removes a single instance of the specified element from this queue, if it is present. More formally, removes an element
e
such that
o.equals(e)
, if this queue contains one or more such elements. Returns true if this queue contained the specified element (or equivalently, if this queue changed as a result of the call).
Adds the specified element to this queue.
-
-
Specified by:
-
remove
add
in interface
Collection
<
E
> -
Overrides:
-
remove
add
in class
AbstractCollection
AbstractQueue
<
E
>
-
-
Parameters:
-
o - element to be removed from this queue, if present
o - the element
-
Returns:
-
true
if this queue changed as a result of the call
(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.
contains
remove
public boolean
contains ![](../../diffpics/oold.gif)
remove (Object o)
-
Returns
true
if this queue contains the specified element. More formally, returns
true
if and only if this queue contains at least one element
e
such that
o.equals(e)
.
Removes a single instance of the specified element from this queue, if it is present.
-
-
Specified by:
-
contains
remove
in interface
Collection
<
E
> -
Overrides:
-
contains
remove
in class
AbstractCollection
<
E
>
-
-
Parameters:
-
o - object to be checked for containment in this queue
o - element to be removed from this collection, if present.
-
Returns:
-
true
if this queue contains the specified element
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
queue.
size
public int size()
-
Description copied from
interface:
Collection
class:
AbstractCollection
-
Returns the number of elements in this collection. If
this
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
collection.
clear
public void clear()
-
Removes all
of the
elements from
this
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
returns
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
empty.
comparator
public Comparator<? super E> comparator()
-
Returns the comparator used to order
the elements in
this
queue,
collection,
or
null
if this queue is sorted according to the
natural ordering
of its elements.
if this collection is sorted according to its elements natural ordering (using
Comparable
).
-
-
-
Returns:
-
the comparator used to order this
queue,
collection,
or
null
if this
queue
collection
is sorted according to
the
its elements
natural
ordering of its elements.
ordering.