Docjar: A Java Source and Docuemnt Enginecom.*    java.*    javax.*    org.*    all    new    plug-in

Quick Search    Search Deep

edu.emory.mathcs.util
Class PriorityQueue  view PriorityQueue download PriorityQueue.java

java.lang.Object
  extended byjava.util.AbstractCollection
      extended byedu.emory.mathcs.util.AbstractQueue
          extended byedu.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 leaf-node 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 one-based array is used in preference to the traditional zero-based 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.

Specified by:
poll in interface Queue

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.

Specified by:
peek in interface 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 interface java.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 interface java.util.Collection

size

public int size()
Returns the number of elements in this priority queue.

Specified by:
size in interface java.util.Collection

offer

public boolean offer(java.lang.Object element)
Add the specified element to this priority queue.

Specified by:
offer in interface Queue

clear

public void clear()
Remove all elements from the priority queue.

Specified by:
clear in interface java.util.Collection
Overrides:
clear in class AbstractQueue

remove

private java.lang.Object remove(int i)
Removes and returns the ith element from queue. Recall that queue is one-based, so 1 <= i <= size. XXX: Could further special-case i==size, but is it worth it? XXX: Could special-case 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 leaf-node 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).