File	Doc	Category	Size	Date	Package
PriorityQueue.java	API Doc	Java SE 6 API	25779	Tue Jun 10 00:25:54 BST 2008	java.util

PriorityQueue

• java.lang.Object
  • java.util.AbstractCollection
    • java.util.AbstractQueue

Fields Summary
private static final long	serialVersionUID
private static final int	DEFAULT_INITIAL_CAPACITY
private transient Object[]	queue Priority queue represented as a balanced binary heap: the two children of queue[n] are queue[2*n+1] 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[0], assuming the queue is nonempty.
private int	size The number of elements in the priority queue.
private final Comparator	comparator The comparator, or null if priority queue uses elements' natural ordering.
private transient int	modCount The number of times this priority queue has been structurally modified. See AbstractList for gory details.

Constructors Summary
public PriorityQueue() Creates a {@code PriorityQueue} with the default initial capacity (11) that orders its elements according to their {@linkplain Comparable natural ordering}. this(DEFAULT_INITIAL_CAPACITY, null);
public PriorityQueue(int initialCapacity) Creates a {@code PriorityQueue} with the specified initial capacity that orders its elements according to their {@linkplain Comparable natural ordering}. param initialCapacity the initial capacity for this priority queue throws IllegalArgumentException if {@code initialCapacity} is less than 1 this(initialCapacity, null);
public PriorityQueue(int initialCapacity, Comparator comparator) Creates a {@code PriorityQueue} with the specified initial capacity that orders its elements according to the specified comparator. param initialCapacity the initial capacity for this priority queue param comparator the comparator that will be used to order this priority queue. If {@code null}, the {@linkplain Comparable natural ordering} of the elements will be used. throws IllegalArgumentException if {@code initialCapacity} is less than 1 // Note: This restriction of at least one is not actually needed, // but continues for 1.5 compatibility if (initialCapacity < 1) throw new IllegalArgumentException(); this.queue = new Object[initialCapacity]; this.comparator = comparator;
public PriorityQueue(Collection c) Creates a {@code PriorityQueue} containing the elements in the specified collection. If the specified collection is an instance of a {@link SortedSet} or is another {@code PriorityQueue}, this priority queue will be ordered according to the same ordering. Otherwise, this priority queue will be ordered according to the {@linkplain Comparable natural ordering} of its elements. param 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 throws NullPointerException if the specified collection or any of its elements are null initFromCollection(c); if (c instanceof SortedSet) comparator = (Comparator<? super E>) ((SortedSet<? extends E>)c).comparator(); else if (c instanceof PriorityQueue) comparator = (Comparator<? super E>) ((PriorityQueue<? extends E>)c).comparator(); else { comparator = null; heapify(); }
public PriorityQueue(PriorityQueue c) Creates a {@code PriorityQueue} containing the elements in the specified priority queue. This priority queue will be ordered according to the same ordering as the given priority queue. param c the priority queue whose elements are to be placed into this priority queue throws ClassCastException if elements of {@code c} cannot be compared to one another according to {@code c}'s ordering throws NullPointerException if the specified priority queue or any of its elements are null comparator = (Comparator<? super E>)c.comparator(); initFromCollection(c);
public PriorityQueue(SortedSet c) Creates a {@code PriorityQueue} containing the elements in the specified sorted set. This priority queue will be ordered according to the same ordering as the given sorted set. param c the sorted set whose elements are to be placed into this priority queue throws ClassCastException if elements of the specified sorted set cannot be compared to one another according to the sorted set's ordering throws NullPointerException if the specified sorted set or any of its elements are null comparator = (Comparator<? super E>)c.comparator(); initFromCollection(c);

Methods Summary
public boolean	add(E e) Inserts the specified element into this priority queue. return {@code true} (as specified by {@link Collection#add}) throws ClassCastException if the specified element cannot be compared with elements currently in this priority queue according to the priority queue's ordering throws NullPointerException if the specified element is null return offer(e);
public void	clear() Removes all of the elements from this priority queue. The queue will be empty after this call returns. modCount++; for (int i = 0; i < size; i++) queue[i] = null; size = 0;
public java.util.Comparator	comparator() Returns the comparator used to order the elements in this queue, or {@code null} if this queue is sorted according to the {@linkplain Comparable natural ordering} of its elements. return the comparator used to order this queue, or {@code null} if this queue is sorted according to the natural ordering of its elements return comparator;
public boolean	contains(java.lang.Object o) Returns {@code true} if this queue contains the specified element. More formally, returns {@code true} if and only if this queue contains at least one element {@code e} such that {@code o.equals(e)}. param o object to be checked for containment in this queue return {@code true} if this queue contains the specified element return indexOf(o) != -1;
private void	grow(int minCapacity) Increases the capacity of the array. param minCapacity the desired minimum capacity if (minCapacity < 0) // overflow throw new OutOfMemoryError(); int oldCapacity = queue.length; // Double size if small; else grow by 50% int newCapacity = ((oldCapacity < 64)? ((oldCapacity + 1) * 2): ((oldCapacity / 2) * 3)); if (newCapacity < 0) // overflow newCapacity = Integer.MAX_VALUE; if (newCapacity < minCapacity) newCapacity = minCapacity; queue = Arrays.copyOf(queue, newCapacity);
private void	heapify() Establishes the heap invariant (described above) in the entire tree, assuming nothing about the order of the elements prior to the call. for (int i = (size >>> 1) - 1; i >= 0; i--) siftDown(i, (E) queue[i]);
private int	indexOf(java.lang.Object o) if (o != null) { for (int i = 0; i < size; i++) if (o.equals(queue[i])) return i; } return -1;
private void	initFromCollection(java.util.Collection c) Initializes queue array with elements from the given Collection. param c the collection Object[] a = c.toArray(); // If c.toArray incorrectly doesn't return Object[], copy it. if (a.getClass() != Object[].class) a = Arrays.copyOf(a, a.length, Object[].class); queue = a; size = a.length;
public java.util.Iterator	iterator() Returns an iterator over the elements in this queue. The iterator does not return the elements in any particular order. return an iterator over the elements in this queue return new Itr();
public boolean	offer(E e) Inserts the specified element into this priority queue. return {@code true} (as specified by {@link Queue#offer}) throws ClassCastException if the specified element cannot be compared with elements currently in this priority queue according to the priority queue's ordering throws NullPointerException if the specified element is null if (e == null) throw new NullPointerException(); modCount++; int i = size; if (i >= queue.length) grow(i + 1); size = i + 1; if (i == 0) queue[0] = e; else siftUp(i, e); return true;
public E	peek() if (size == 0) return null; return (E) queue[0];
public E	poll() if (size == 0) return null; int s = --size; modCount++; E result = (E) queue[0]; E x = (E) queue[s]; queue[s] = null; if (s != 0) siftDown(0, x); return result;
private void	readObject(java.io.ObjectInputStream s) Reconstitutes the {@code PriorityQueue} instance from a stream (that is, deserializes it). param s the stream // Read in size, and any hidden stuff s.defaultReadObject(); // Read in (and discard) array length s.readInt(); queue = new Object[size]; // Read in all elements. for (int i = 0; i < size; i++) queue[i] = s.readObject(); // Elements are guaranteed to be in "proper order", but the // spec has never explained what that might be. heapify();
public boolean	remove(java.lang.Object o) Removes a single instance of the specified element from this queue, if it is present. More formally, removes an element {@code e} such that {@code o.equals(e)}, if this queue contains one or more such elements. Returns {@code true} if and only if this queue contained the specified element (or equivalently, if this queue changed as a result of the call). param o element to be removed from this queue, if present return {@code true} if this queue changed as a result of the call int i = indexOf(o); if (i == -1) return false; else { removeAt(i); return true; }
private E	removeAt(int i) Removes the ith element from queue. Normally this method leaves the elements at up to i-1, inclusive, untouched. Under these circumstances, it returns null. Occasionally, in order to maintain the heap invariant, it must swap a later element of the list with one earlier than i. Under these circumstances, this method returns the element that was previously at the end of the list and is now at some position before i. This fact is used by iterator.remove so as to avoid missing traversing elements. assert i >= 0 && i < size; modCount++; int s = --size; if (s == i) // removed last element queue[i] = null; else { E moved = (E) queue[s]; queue[s] = null; siftDown(i, moved); if (queue[i] == moved) { siftUp(i, moved); if (queue[i] != moved) return moved; } } return null;
boolean	removeEq(java.lang.Object o) Version of remove using reference equality, not equals. Needed by iterator.remove. param o element to be removed from this queue, if present return {@code true} if removed for (int i = 0; i < size; i++) { if (o == queue[i]) { removeAt(i); return true; } } return false;
private void	siftDown(int k, E x) Inserts item x at position k, maintaining heap invariant by demoting x down the tree repeatedly until it is less than or equal to its children or is a leaf. param k the position to fill param x the item to insert if (comparator != null) siftDownUsingComparator(k, x); else siftDownComparable(k, x);
private void	siftDownComparable(int k, E x) Comparable<? super E> key = (Comparable<? super E>)x; int half = size >>> 1; // loop while a non-leaf while (k < half) { int child = (k << 1) + 1; // assume left child is least Object c = queue[child]; int right = child + 1; if (right < size && ((Comparable<? super E>) c).compareTo((E) queue[right]) > 0) c = queue[child = right]; if (key.compareTo((E) c) <= 0) break; queue[k] = c; k = child; } queue[k] = key;
private void	siftDownUsingComparator(int k, E x) int half = size >>> 1; while (k < half) { int child = (k << 1) + 1; Object c = queue[child]; int right = child + 1; if (right < size && comparator.compare((E) c, (E) queue[right]) > 0) c = queue[child = right]; if (comparator.compare(x, (E) c) <= 0) break; queue[k] = c; k = child; } queue[k] = x;
private void	siftUp(int k, E x) Inserts item x at position k, maintaining heap invariant by promoting x up the tree until it is greater than or equal to its parent, or is the root. To simplify and speed up coercions and comparisons. the Comparable and Comparator versions are separated into different methods that are otherwise identical. (Similarly for siftDown.) param k the position to fill param x the item to insert if (comparator != null) siftUpUsingComparator(k, x); else siftUpComparable(k, x);
private void	siftUpComparable(int k, E x) Comparable<? super E> key = (Comparable<? super E>) x; while (k > 0) { int parent = (k - 1) >>> 1; Object e = queue[parent]; if (key.compareTo((E) e) >= 0) break; queue[k] = e; k = parent; } queue[k] = key;
private void	siftUpUsingComparator(int k, E x) while (k > 0) { int parent = (k - 1) >>> 1; Object e = queue[parent]; if (comparator.compare(x, (E) e) >= 0) break; queue[k] = e; k = parent; } queue[k] = x;
public int	size() return size;
public java.lang.Object[]	toArray() Returns an array containing all of the elements in this queue. The elements are in no particular order. The returned array will be "safe" in that no references to it are maintained by this queue. (In other words, this method must allocate a new array). The caller is thus free to modify the returned array. This method acts as bridge between array-based and collection-based APIs. return an array containing all of the elements in this queue return Arrays.copyOf(queue, size);
public T[]	toArray(T[] a) Returns an array containing all of the elements in this queue; the runtime type of the returned array is that of the specified array. The returned array elements are in no particular order. If the queue fits in the specified array, it is returned therein. Otherwise, a new array is allocated with the runtime type of the specified array and the size of this queue. If the queue fits in the specified array with room to spare (i.e., the array has more elements than the queue), the element in the array immediately following the end of the collection is set to {@code null}. Like the {@link #toArray()} method, this method acts as bridge between array-based and collection-based APIs. Further, this method allows precise control over the runtime type of the output array, and may, under certain circumstances, be used to save allocation costs. Suppose x is a queue known to contain only strings. The following code can be used to dump the queue into a newly allocated array of String: String[] y = x.toArray(new String[0]); Note that toArray(new Object[0]) is identical in function to toArray(). param a the array into which the elements of the queue are to be stored, if it is big enough; otherwise, a new array of the same runtime type is allocated for this purpose. return an array containing all of the elements in this queue throws ArrayStoreException if the runtime type of the specified array is not a supertype of the runtime type of every element in this queue throws NullPointerException if the specified array is null if (a.length < size) // Make a new array of a's runtime type, but my contents: return (T[]) Arrays.copyOf(queue, size, a.getClass()); System.arraycopy(queue, 0, a, 0, size); if (a.length > size) a[size] = null; return a;
private void	writeObject(java.io.ObjectOutputStream s) Saves the state of the instance to a stream (that is, serializes it). serialData The length of the array backing the instance is emitted (int), followed by all of its elements (each an {@code Object}) in the proper order. param s the stream // Write out element count, and any hidden stuff s.defaultWriteObject(); // Write out array length, for compatibility with 1.5 version s.writeInt(Math.max(2, size + 1)); // Write out all elements in the "proper order". for (int i = 0; i < size; i++) s.writeObject(queue[i]);