File	Doc	Category	Size	Date	Package
PriorityQueue.java	API Doc	Java SE 5 API	23290	Fri Aug 26 14:57:24 BST 2005	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] 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.
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 PriorityQueue with the default initial capacity (11) that orders its elements according to their natural ordering (using Comparable). this(DEFAULT_INITIAL_CAPACITY, null);
public PriorityQueue(int initialCapacity) Creates a PriorityQueue with the specified initial capacity that orders its elements according to their natural ordering (using Comparable). param initialCapacity the initial capacity for this priority queue. throws IllegalArgumentException if initialCapacity is less than 1 this(initialCapacity, null);
public PriorityQueue(int initialCapacity, Comparator comparator) Creates a 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 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 if (initialCapacity < 1) throw new IllegalArgumentException(); this.queue = new Object[initialCapacity + 1]; this.comparator = comparator;
public PriorityQueue(Collection 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 {@link java.util.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. 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 c or any element within it is null initializeArray(c); if (c instanceof SortedSet) { SortedSet<? extends E> s = (SortedSet<? extends E>)c; comparator = (Comparator<? super E>)s.comparator(); fillFromSorted(s); } else if (c instanceof PriorityQueue) { PriorityQueue<? extends E> s = (PriorityQueue<? extends E>) c; comparator = (Comparator<? super E>)s.comparator(); fillFromSorted(s); } else { comparator = null; fillFromUnsorted(c); }
public PriorityQueue(PriorityQueue 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. 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 c or any element within it is null initializeArray(c); comparator = (Comparator<? super E>)c.comparator(); fillFromSorted(c);
public PriorityQueue(SortedSet 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. 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 c or any element within it is null initializeArray(c); comparator = (Comparator<? super E>)c.comparator(); fillFromSorted(c);

Methods Summary
public boolean	add(E o) Adds the specified element to this queue. return true (as per the general contract of Collection.add). throws NullPointerException if the specified element is null. throws ClassCastException if the specified element cannot be compared with elements currently in the priority queue according to the priority queue's ordering. return offer(o);
public void	clear() Removes all elements from the priority queue. The queue will be empty after this call returns. modCount++; // Null out element references to prevent memory leak for (int i=1; i<=size; i++) queue[i] = null; size = 0;
public java.util.Comparator	comparator() Returns the comparator used to order this collection, or null if this collection is sorted according to its elements natural ordering (using Comparable). return the comparator used to order this collection, or null if this collection is sorted according to its elements natural ordering. return comparator;
private void	fillFromSorted(java.util.Collection c) Initially fill elements of the queue array under the knowledge that it is sorted or is another PQ, in which case we can just place the elements in the order presented. for (Iterator<? extends E> i = c.iterator(); i.hasNext(); ) queue[++size] = i.next();
private void	fillFromUnsorted(java.util.Collection c) Initially fill elements of the queue array that is not to our knowledge sorted, so we must rearrange the elements to guarantee the heap invariant. for (Iterator<? extends E> i = c.iterator(); i.hasNext(); ) queue[++size] = i.next(); heapify();
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. int j; if (comparator == null) { while ((j = k << 1) <= size && (j > 0)) { if (j<size && ((Comparable<E>)queue[j]).compareTo((E)queue[j+1]) > 0) j++; // j indexes smallest kid if (((Comparable<E>)queue[k]).compareTo((E)queue[j]) <= 0) break; Object tmp = queue[j]; queue[j] = queue[k]; queue[k] = tmp; k = j; } } else { while ((j = k << 1) <= size && (j > 0)) { if (j<size && comparator.compare((E)queue[j], (E)queue[j+1]) > 0) j++; // j indexes smallest kid if (comparator.compare((E)queue[k], (E)queue[j]) <= 0) break; Object tmp = queue[j]; queue[j] = queue[k]; queue[k] = tmp; k = j; } }
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. if (comparator == null) { while (k > 1) { int j = k >> 1; if (((Comparable<E>)queue[j]).compareTo((E)queue[k]) <= 0) break; Object tmp = queue[j]; queue[j] = queue[k]; queue[k] = tmp; k = j; } } else { while (k > 1) { int j = k >>> 1; if (comparator.compare((E)queue[j], (E)queue[k]) <= 0) break; Object tmp = queue[j]; queue[j] = queue[k]; queue[k] = tmp; k = j; } }
private void	grow(int index) Resize array, if necessary, to be able to hold given index int newlen = queue.length; if (index < newlen) // don't need to grow return; if (index == Integer.MAX_VALUE) throw new OutOfMemoryError(); while (newlen <= index) { if (newlen >= Integer.MAX_VALUE / 2) // avoid overflow newlen = Integer.MAX_VALUE; else newlen <<= 2; } Object[] newQueue = new Object[newlen]; System.arraycopy(queue, 0, newQueue, 0, queue.length); queue = newQueue;
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/2; i >= 1; i--) fixDown(i);
private void	initializeArray(java.util.Collection c) Common code to initialize underlying queue array across constructors below. int sz = c.size(); int initialCapacity = (int)Math.min((sz * 110L) / 100, Integer.MAX_VALUE - 1); if (initialCapacity < 1) initialCapacity = 1; this.queue = new Object[initialCapacity + 1];
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 o) Inserts the specified element into this priority queue. return true throws ClassCastException if the specified element cannot be compared with elements currently in the priority queue according to the priority queue's ordering. throws NullPointerException if the specified element is null. if (o == null) throw new NullPointerException(); modCount++; ++size; // Grow backing store if necessary if (size >= queue.length) grow(size); queue[size] = o; fixUp(size); return true;
public E	peek() if (size == 0) return null; return (E) queue[1];
public E	poll() if (size == 0) return null; modCount++; E result = (E) queue[1]; queue[1] = queue[size]; queue[size--] = null; // Drop extra ref to prevent memory leak if (size > 1) fixDown(1); return result;
private void	readObject(java.io.ObjectInputStream s) Reconstitute the ArrayList instance from a stream (that is, deserialize it). param s the stream // Read in size, and any hidden stuff s.defaultReadObject(); // Read in array length and allocate array int arrayLength = s.readInt(); queue = new Object[arrayLength]; // Read in all elements in the proper order. for (int i=1; i<=size; i++) queue[i] = (E) s.readObject();
public boolean	remove(java.lang.Object o) Removes a single instance of the specified element from this queue, if it is present. if (o == null) return false; if (comparator == null) { for (int i = 1; i <= size; i++) { if (((Comparable<E>)queue[i]).compareTo((E)o) == 0) { removeAt(i); return true; } } } else { for (int i = 1; i <= size; i++) { if (comparator.compare((E)queue[i], (E)o) == 0) { removeAt(i); return true; } } } return false;
private E	removeAt(int i) Removes and returns the ith element from queue. (Recall that queue is one-based, so 1 <= i <= size.) Normally this method leaves the elements at positions from 1 up to i-1, inclusive, untouched. Under these circumstances, it returns null. Occasionally, in order to maintain the heap invariant, it must move the last element of the list to some index in the range [2, i-1], and move the element previously at position (i/2) to position i. Under these circumstances, this method returns the element that was previously at the end of the list and is now at some position between 2 and i-1 inclusive. assert i > 0 && i <= size; modCount++; E moved = (E) queue[size]; queue[i] = moved; queue[size--] = null; // Drop extra ref to prevent memory leak if (i <= size) { fixDown(i); if (queue[i] == moved) { fixUp(i); if (queue[i] != moved) return moved; } } return null;
public int	size() return size;
private void	writeObject(java.io.ObjectOutputStream s) Save the state of the instance to a stream (that is, serialize it). serialData The length of the array backing the instance is emitted (int), followed by all of its elements (each an Object) in the proper order. param s the stream // Write out element count, and any hidden stuff s.defaultWriteObject(); // Write out array length s.writeInt(queue.length); // Write out all elements in the proper order. for (int i=1; i<=size; i++) s.writeObject(queue[i]);