

Home >> All >> edu >> emory >> mathcs >> [ util overview ]  PREV CLASS NEXT CLASS  
SUMMARY: JAVADOC  SOURCE  DOWNLOAD  NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 
edu.emory.mathcs.util
Class PriorityQueue
java.lang.Object java.util.AbstractCollection edu.emory.mathcs.util.AbstractQueue edu.emory.mathcs.util.PriorityQueue
 All Implemented Interfaces:
 java.util.Collection, java.lang.Iterable, Queue, java.io.Serializable
 public class PriorityQueue
 extends AbstractQueue
 implements Queue, java.io.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 in the same manner as java.util.TreeSet and java.util.TreeMap: elements are ordered
either according to their natural order (see java.lang.Comparable), or
according to a java.util.Comparator, depending on which constructor is used.
The peek()
55 , poll()
55 , and remove(java.lang.Object)
55 methods return the
minimal element with respect to the specified ordering. If multiple
elements are tied for least value, no guarantees are made as to
which of these elements is returned.
A priority queue has a capacity. The capacity is the size of the array used internally 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.
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
Nested Class Summary  
private class 
PriorityQueue.Itr

Field Summary  
private java.util.Comparator 
comparator
The comparator, or null if priority queue uses elements' natural ordering. 
private static int 
DEFAULT_INITIAL_CAPACITY

private int 
modCount
The number of times this priority queue has been structurally modified. 
private java.lang.Object[] 
queue
Priority queue represented as a balanced binary heap: the two children of queue[n] are queue[2*n] and queue[2*n + 1]. 
private int 
size
The number of elements in the priority queue. 
Constructor Summary  
PriorityQueue()
Create a new priority queue with the default initial capacity (11) that orders its elements according to their natural ordering (using Comparable.) 

PriorityQueue(java.util.Collection initialElements)
Create a new priority queue containing the elements in the specified collection. 

PriorityQueue(int initialCapacity)
Create a new priority queue with the specified initial capacity that orders its elements according to their natural ordering (using Comparable.) 

PriorityQueue(int initialCapacity,
java.util.Comparator comparator)
Create a new priority queue with the specified initial capacity (11) that orders its elements according to the specified comparator. 
Method Summary  
void 
clear()
Remove all elements from the priority queue. 
java.util.Comparator 
comparator()
Returns the comparator associated with this priority queue, or null if it uses its elements' natural ordering. 
private void 
fixDown(int k)
Establishes the heap invariant (described above) in the subtree rooted at k, which is assumed to satisfy the heap invariant except possibly for node k itself (which may be greater than its children). 
private void 
fixUp(int k)
Establishes the heap invariant (described above) assuming the heap satisfies the invariant except possibly for the leafnode indexed by k (which may have a nextExecutionTime less than its parent's). 
java.util.Iterator 
iterator()
Returns an iterator over the elements in this priority queue. 
boolean 
offer(java.lang.Object element)
Add the specified element to this priority queue. 
java.lang.Object 
peek()
Return, but do not remove, the minimal element from the priority queue, or return null if the queue is empty. 
java.lang.Object 
poll()
Remove and return the minimal element from this priority queue if it contains one or more elements, otherwise return null. 
private void 
readObject(java.io.ObjectInputStream s)
Reconstitute the ArrayList instance from a stream (that is, deserialize it). 
private java.lang.Object 
remove(int i)
Removes and returns the ith element from queue. 
boolean 
remove(java.lang.Object element)
Removes a single instance of the specified element from this priority queue, if it is present. 
int 
size()
Returns the number of elements in this priority queue. 
private void 
writeObject(java.io.ObjectOutputStream s)
Save the state of the instance to a stream (that is, serialize it). 
Methods inherited from class edu.emory.mathcs.util.AbstractQueue 
add, element, remove 
Methods inherited from class java.util.AbstractCollection 
addAll, 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 edu.emory.mathcs.util.Queue 
element, remove 
Methods inherited from interface java.util.Collection 
add, addAll, contains, containsAll, equals, hashCode, isEmpty, removeAll, retainAll, toArray, toArray 
Field Detail 
DEFAULT_INITIAL_CAPACITY
private static final int DEFAULT_INITIAL_CAPACITY
 See Also:
 Constant Field Values
queue
private transient java.lang.Object[] queue
 Priority queue represented as a balanced binary heap: the two children
of queue[n] are queue[2*n] and queue[2*n + 1]. The priority queue is
ordered by comparator, or by the elements' natural ordering, if
comparator is null: For each node n in the heap and each descendant d
of n, n <= d.
The element with the lowest value is in queue[1], assuming the queue is
nonempty. (A onebased array is used in preference to the traditional
zerobased array to simplify parent and child calculations.)
queue.length must be >= 2, even if size == 0.
size
private int size
 The number of elements in the priority queue.
comparator
private final java.util.Comparator comparator
 The comparator, or null if priority queue uses elements'
natural ordering.
modCount
private transient int modCount
 The number of times this priority queue has been
structurally modified. See AbstractList for gory details.
Constructor Detail 
PriorityQueue
public PriorityQueue()
 Create a new priority queue with the default initial capacity
(11) that orders its elements according to their natural
ordering (using Comparable.)
PriorityQueue
public PriorityQueue(int initialCapacity)
 Create a new priority queue with the specified initial capacity
that orders its elements according to their natural ordering
(using Comparable.)
PriorityQueue
public PriorityQueue(int initialCapacity, java.util.Comparator comparator)
 Create a new priority queue with the specified initial capacity (11)
that orders its elements according to the specified comparator.
PriorityQueue
public PriorityQueue(java.util.Collection initialElements)
 Create a new priority queue containing the elements in the specified
collection. The priority queue has an initial capacity of 110% of the
size of the specified collection. If the specified collection
implements the
Sorted
interface, 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. If the specified collection does not implement Sorted, the priority queue is ordered according to its elements' natural order.
Method Detail 
poll
public java.lang.Object poll()
 Remove and return the minimal element from this priority queue
if it contains one or more elements, otherwise return
null. The term minimal is defined according to
this priority queue's order.
peek
public java.lang.Object peek()
 Return, but do not remove, the minimal element from the
priority queue, or return null if the queue is empty.
The term minimal is defined according to this priority
queue's order. This method returns the same object reference
that would be returned by by the poll method. The two
methods differ in that this method does not remove the element
from the priority queue.
remove
public boolean remove(java.lang.Object element)
 Removes a single instance of the specified element from this priority
queue, if it is present. Returns true if this collection contained the
specified element (or equivalently, if this collection changed as a
result of the call).
 Specified by:
remove
in interfacejava.util.Collection
iterator
public java.util.Iterator iterator()
 Returns an iterator over the elements in this priority queue. The
elements of the priority queue will be returned by this iterator in the
order specified by the queue, which is to say the order they would be
returned by repeated calls to poll.
 Specified by:
iterator
in interfacejava.util.Collection
size
public int size()
 Returns the number of elements in this priority queue.
 Specified by:
size
in interfacejava.util.Collection
offer
public boolean offer(java.lang.Object element)
clear
public void clear()
 Remove all elements from the priority queue.
 Specified by:
clear
in interfacejava.util.Collection
 Overrides:
clear
in classAbstractQueue
remove
private java.lang.Object remove(int i)
 Removes and returns the ith element from queue. Recall
that queue is onebased, so 1 <= i <= size.
XXX: Could further specialcase i==size, but is it worth it?
XXX: Could specialcase i==0, but is it worth it?
fixUp
private void fixUp(int k)
 Establishes the heap invariant (described above) assuming the heap
satisfies the invariant except possibly for the leafnode indexed by k
(which may have a nextExecutionTime less than its parent's).
This method functions by "promoting" queue[k] up the hierarchy
(by swapping it with its parent) repeatedly until queue[k]
is greater than or equal to its parent.
fixDown
private void fixDown(int k)
 Establishes the heap invariant (described above) in the subtree
rooted at k, which is assumed to satisfy the heap invariant except
possibly for node k itself (which may be greater than its children).
This method functions by "demoting" queue[k] down the hierarchy
(by swapping it with its smaller child) repeatedly until queue[k]
is less than or equal to its children.
comparator
public java.util.Comparator comparator()
 Returns the comparator associated with this priority queue, or
null if it uses its elements' natural ordering.
writeObject
private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException
 Save the state of the instance to a stream (that
is, serialize it).
readObject
private void readObject(java.io.ObjectInputStream s) throws java.io.IOException, java.lang.ClassNotFoundException
 Reconstitute the ArrayList instance from a stream (that is,
deserialize it).


Home >> All >> edu >> emory >> mathcs >> [ util overview ]  PREV CLASS NEXT CLASS  
SUMMARY: JAVADOC  SOURCE  DOWNLOAD  NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 