java/util/PriorityQueue.java

 package java.util;

/**
 * A 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 {@link java.util.TreeSet} and
 * {@link java.util.TreeMap}: elements are ordered
 * either according to their <i>natural order</i> (see {@link Comparable}), or
 * according to a {@link java.util.Comparator}, depending on which
 * constructor is used.
 * <p>The <em>head</em> of this queue is the <em>least</em> element with
 * respect to the specified ordering.
 * If multiple elements are tied for least value, the
 * head is one of those elements. A priority queue does not permit
 * <tt>null</tt> elements.
 *
 * <p>The {@link #remove()} and {@link #poll()} methods remove and
 * return the head of the queue.
 *
 * <p>The {@link #element()} and {@link #peek()} methods return, but do
 * not delete, the head of the queue.
 *
 * <p>A priority queue has a <i>capacity</i>.  The capacity is the
 * size of the array used internally to store the elements on the
 * queue, and is limited to <tt>Integer.MAX_VALUE-1</tt>.
 * 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.
 *
 * <p>Implementation note: this implementation provides O(log(n)) time
 * for the insertion methods (<tt>offer</tt>, <tt>poll</tt>,
 * <tt>remove()</tt> and <tt>add</tt>) methods; linear time for the
 * <tt>remove(Object)</tt> and <tt>contains(Object)</tt> methods; and
 * constant time for the retrieval methods (<tt>peek</tt>,
 * <tt>element</tt>, and <tt>size</tt>).
 *
 * <p>This class is a member of the
 * <a href="{@docRoot}/../guide/collections/index.html">
 * Java Collections Framework</a>.
 * @since 1.5
 * @author Josh Bloch
 */
public class PriorityQueue<E> extends AbstractQueue<E>
    implements Sorted, Queue<E>, java.io.Serializable {

    private static final int DEFAULT_INITIAL_CAPACITY = 11;

    /**
     * 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 transient Object[] queue;

    /**
     * The number of elements in the priority queue.
     */
    private int size = 0;

    /**
     * The comparator, or null if priority queue uses elements'
     * natural ordering.
     */
    private final Comparator<? super E> comparator;

    /**
     * The number of times this priority queue has been
     * <i>structurally modified</i>.  See AbstractList for gory details.
     */
    private transient int modCount = 0;

    /**
     * Create a <tt>PriorityQueue</tt> with the default initial capacity
     * (11) that orders its elements according to their natural
     * ordering (using <tt>Comparable</tt>.)
     */
    public PriorityQueue() {
        this(DEFAULT_INITIAL_CAPACITY, null);
    }

    /**
     * Create a <tt>PriorityQueue</tt> with the specified initial capacity
     * that orders its elements according to their natural ordering
     * (using <tt>Comparable</tt>.)
     *
     * @param initialCapacity the initial capacity for this priority queue.
     */
    public PriorityQueue(int initialCapacity) {
        this(initialCapacity, null);
    }

    /**
     * Create a <tt>PriorityQueue</tt> 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 <tt>null</tt> then the order depends on the elements' natural
     * ordering.
     * @throws IllegalArgumentException if <tt>initialCapacity</tt> is less
     * than 1
     */
    public PriorityQueue(int initialCapacity, Comparator<? super E> comparator) {
        if (initialCapacity < 1)
            throw new IllegalArgumentException();
        this.queue = new Object[initialCapacity + 1];
        this.comparator = comparator;
    }

    /**
     * Create a <tt>PriorityQueue</tt> containing the elements in the specified
     * collection.  The priority queue has an initial capacity of 110% of the
     * size of the specified collection (bounded by
     * <tt>Integer.MAX_VALUE-1</tt>); or 1 if the collection is empty.
     * If the specified collection
     * implements the {@link 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
     * <tt>Sorted</tt>, 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 <tt>c</tt> or any element within it
     * is <tt>null</tt>
     */
    public PriorityQueue(Collection<? extends E> c) {
        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];

        // FIXME: if c is larger than Integer.MAX_VALUE we'll
        // overflow the array

        if (c instanceof Sorted) {
            comparator = (Comparator<? super E>)((Sorted)c).comparator();
        } else {
            comparator = null;
        }

        for (Iterator<? extends E> i = c.iterator(); i.hasNext(); )
            add(i.next());
    }

    // Queue Methods

    /**
     * Add the specified element to this priority queue.
     *
     * @return <tt>true</tt>
     * @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 <tt>null</tt>.
     */
    public boolean offer(E o) {
        if (o == null)
            throw new NullPointerException();
        modCount++;
        ++size;

        // Grow backing store if necessary
        // FIXME: watch for overflow
        // FIXME: what if we're full?
        while (size >= queue.length) {
            Object[] newQueue = new Object[2 * queue.length];
            System.arraycopy(queue, 0, newQueue, 0, queue.length);
            queue = newQueue;
        }

        queue[size] = o;
        fixUp(size);
        return true;
    }

    public E poll() {
        if (size == 0)
            return null;
        return (E) remove(1);
    }

    public E peek() {
        return (E) queue[1];
    }

    // Collection Methods

    // these first two override just to get the throws docs

    /**
     * @throws NullPointerException if the specified element is <tt>null</tt>.
     * @throws ClassCastException if the specified element cannot be compared
     * with elements currently in the priority queue according
     * to the priority queue's ordering.
     */
    public boolean add(E o) {
        return super.add(o);
    }

    /**
     * @throws ClassCastException if any element cannot be compared
     * with elements currently in the priority queue according
     * to the priority queue's ordering.
     * @throws NullPointerException if <tt>c</tt> or any element in <tt>c</tt>
     * is <tt>null</tt>
     */
    public boolean addAll(Collection<? extends E> c) {
        return super.addAll(c);
    }

    public boolean remove(Object o) {
        if (o == null)
            return false;

        if (comparator == null) {
            for (int i = 1; i <= size; i++) {
                if (((Comparable<E>)queue[i]).compareTo((E)o) == 0) {
                    remove(i);
                    return true;
                }
            }
        } else {
            for (int i = 1; i <= size; i++) {
                if (comparator.compare((E)queue[i], (E)o) == 0) {
                    remove(i);
                    return true;
                }
            }
        }
        return false;
    }

    public Iterator<E> iterator() {
        return new Itr();
    }

    private class Itr implements Iterator<E> {
        /**
         * Index (into queue array) of element to be returned by
         * subsequent call to next.
         */
        private int cursor = 1;

        /**
         * Index of element returned by most recent call to next or
         * previous.  Reset to 0 if this element is deleted by a call
         * to remove.
         */
        private int lastRet = 0;

        /**
         * The modCount value that the iterator believes that the backing
         * List should have.  If this expectation is violated, the iterator
         * has detected concurrent modification.
         */
        private int expectedModCount = modCount;

        public boolean hasNext() {
            return cursor <= size;
        }

        public E next() {
            checkForComodification();
            if (cursor > size)
                throw new NoSuchElementException();
            E result = (E) queue[cursor];
            lastRet = cursor++;
            return result;
        }

        public void remove() {
            if (lastRet == 0)
                throw new IllegalStateException();
            checkForComodification();

            PriorityQueue.this.remove(lastRet);
            if (lastRet < cursor)
                cursor--;
            lastRet = 0;
            expectedModCount = modCount;
        }

        final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }
    }

    /**
     * Returns the number of elements in this priority queue.
     *
     * @return the number of elements in this priority queue.
     */
    public int size() {
        return size;
    }

    /**
     * Remove all elements from the priority queue.
     */
    public void clear() {
        modCount++;

        // Null out element references to prevent memory leak
        for (int i=1; i<=size; i++)
            queue[i] = null;

        size = 0;
    }

    /**
     * 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?
     */
    private E remove(int i) {
        assert i <= size;
        modCount++;

        E result = (E) queue[i];
        queue[i] = queue[size];
        queue[size--] = null;  // Drop extra ref to prevent memory leak
        if (i <= size)
            fixDown(i);
        return result;
    }

    /**
     * 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.
     */
    private void fixUp(int k) {
        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;
            }
        }
    }

    /**
     * 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.
     */
    private void fixDown(int k) {
        int j;
        if (comparator == null) {
            while ((j = k << 1) <= size) {
                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) {
                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;
            }
        }
    }

    public Comparator<? super E> comparator() {
        return comparator;
    }

    /**
     * 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
     * <tt>Object</tt>) in the proper order.
     * @param s the stream
     */
    private synchronized void writeObject(java.io.ObjectOutputStream s)
        throws java.io.IOException{
        // 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=0; i<size; i++)
            s.writeObject(queue[i]);
    }

    /**
     * Reconstitute the <tt>ArrayList</tt> instance from a stream (that is,
     * deserialize it).
     * @param s the stream
     */
    private synchronized void readObject(java.io.ObjectInputStream s)
        throws java.io.IOException, ClassNotFoundException {
        // 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=0; i<size; i++)
            queue[i] = s.readObject();
    }

}

Revision:	1.19
Committed:	Mon Aug 4 16:14:48 2003 UTC (20 years, 9 months ago) by tim
Branch:	MAIN
Changes since 1.18:	+9 -9 lines
Log Message:	Make atomics emulation classes match the main atomics. Fix docs for atomics (both in main and emulation). Restored more specific iterator types in both blocking queue impls. Fix unchecked cast warning in PQ.
#	Content
1	package java.util;
2
3	/**
4	* A priority queue based on a priority heap. This queue orders
5	* elements according to an order specified at construction time, which is
6	* specified in the same manner as {@link java.util.TreeSet} and
7	* {@link java.util.TreeMap}: elements are ordered
8	* either according to their <i>natural order</i> (see {@link Comparable}), or
9	* according to a {@link java.util.Comparator}, depending on which
10	* constructor is used.
11	* <p>The <em>head</em> of this queue is the <em>least</em> element with
12	* respect to the specified ordering.
13	* If multiple elements are tied for least value, the
14	* head is one of those elements. A priority queue does not permit
15	* <tt>null</tt> elements.
16	*
17	* <p>The {@link #remove()} and {@link #poll()} methods remove and
18	* return the head of the queue.
19	*
20	* <p>The {@link #element()} and {@link #peek()} methods return, but do
21	* not delete, the head of the queue.
22	*
23	* <p>A priority queue has a <i>capacity</i>. The capacity is the
24	* size of the array used internally to store the elements on the
25	* queue, and is limited to <tt>Integer.MAX_VALUE-1</tt>.
26	* It is always at least as large as the queue size. As
27	* elements are added to a priority queue, its capacity grows
28	* automatically. The details of the growth policy are not specified.
29	*
30	* <p>Implementation note: this implementation provides O(log(n)) time
31	* for the insertion methods (<tt>offer</tt>, <tt>poll</tt>,
32	* <tt>remove()</tt> and <tt>add</tt>) methods; linear time for the
33	* <tt>remove(Object)</tt> and <tt>contains(Object)</tt> methods; and
34	* constant time for the retrieval methods (<tt>peek</tt>,
35	* <tt>element</tt>, and <tt>size</tt>).
36	*
37	* <p>This class is a member of the
38	* <a href="{@docRoot}/../guide/collections/index.html">
39	* Java Collections Framework</a>.
40	* @since 1.5
41	* @author Josh Bloch
42	*/
43	public class PriorityQueue<E> extends AbstractQueue<E>
44	implements Sorted, Queue<E>, java.io.Serializable {
45
46	private static final int DEFAULT_INITIAL_CAPACITY = 11;
47
48	/**
49	* Priority queue represented as a balanced binary heap: the two children
50	* of queue[n] are queue[2n] and queue[2n + 1]. The priority queue is
51	* ordered by comparator, or by the elements' natural ordering, if
52	* comparator is null: For each node n in the heap and each descendant d
53	* of n, n <= d.
54	*
55	* The element with the lowest value is in queue[1], assuming the queue is
56	* nonempty. (A one-based array is used in preference to the traditional
57	* zero-based array to simplify parent and child calculations.)
58	*
59	* queue.length must be >= 2, even if size == 0.
60	*/
61	private transient Object[] queue;
62
63	/**
64	* The number of elements in the priority queue.
65	*/
66	private int size = 0;
67
68	/**
69	* The comparator, or null if priority queue uses elements'
70	* natural ordering.
71	*/
72	private final Comparator<? super E> comparator;
73
74	/**
75	* The number of times this priority queue has been
76	* <i>structurally modified</i>. See AbstractList for gory details.
77	*/
78	private transient int modCount = 0;
79
80	/**
81	* Create a <tt>PriorityQueue</tt> with the default initial capacity
82	* (11) that orders its elements according to their natural
83	* ordering (using <tt>Comparable</tt>.)
84	*/
85	public PriorityQueue() {
86	this(DEFAULT_INITIAL_CAPACITY, null);
87	}
88
89	/**
90	* Create a <tt>PriorityQueue</tt> with the specified initial capacity
91	* that orders its elements according to their natural ordering
92	* (using <tt>Comparable</tt>.)
93	*
94	* @param initialCapacity the initial capacity for this priority queue.
95	*/
96	public PriorityQueue(int initialCapacity) {
97	this(initialCapacity, null);
98	}
99
100	/**
101	* Create a <tt>PriorityQueue</tt> with the specified initial capacity
102	* that orders its elements according to the specified comparator.
103	*
104	* @param initialCapacity the initial capacity for this priority queue.
105	* @param comparator the comparator used to order this priority queue.
106	* If <tt>null</tt> then the order depends on the elements' natural
107	* ordering.
108	* @throws IllegalArgumentException if <tt>initialCapacity</tt> is less
109	* than 1
110	*/
111	public PriorityQueue(int initialCapacity, Comparator<? super E> comparator) {
112	if (initialCapacity < 1)
113	throw new IllegalArgumentException();
114	this.queue = new Object[initialCapacity + 1];
115	this.comparator = comparator;
116	}
117
118	/**
119	* Create a <tt>PriorityQueue</tt> containing the elements in the specified
120	* collection. The priority queue has an initial capacity of 110% of the
121	* size of the specified collection (bounded by
122	* <tt>Integer.MAX_VALUE-1</tt>); or 1 if the collection is empty.
123	* If the specified collection
124	* implements the {@link Sorted} interface, the priority queue will be
125	* sorted according to the same comparator, or according to its elements'
126	* natural order if the collection is sorted according to its elements'
127	* natural order. If the specified collection does not implement
128	* <tt>Sorted</tt>, the priority queue is ordered according to
129	* its elements' natural order.
130	*
131	* @param c the collection whose elements are to be placed
132	* into this priority queue.
133	* @throws ClassCastException if elements of the specified collection
134	* cannot be compared to one another according to the priority
135	* queue's ordering.
136	* @throws NullPointerException if <tt>c</tt> or any element within it
137	* is <tt>null</tt>
138	*/
139	public PriorityQueue(Collection<? extends E> c) {
140	int sz = c.size();
141	int initialCapacity = (int)Math.min((sz * 110L) / 100,
142	Integer.MAX_VALUE - 1);
143	if (initialCapacity < 1)
144	initialCapacity = 1;
145
146	this.queue = new Object[initialCapacity + 1];
147
148	// FIXME: if c is larger than Integer.MAX_VALUE we'll
149	// overflow the array
150
151	if (c instanceof Sorted) {
152	comparator = (Comparator<? super E>)((Sorted)c).comparator();
153	} else {
154	comparator = null;
155	}
156
157	for (Iterator<? extends E> i = c.iterator(); i.hasNext(); )
158	add(i.next());
159	}
160
161	// Queue Methods
162
163	/**
164	* Add the specified element to this priority queue.
165	*
166	* @return <tt>true</tt>
167	* @throws ClassCastException if the specified element cannot be compared
168	* with elements currently in the priority queue according
169	* to the priority queue's ordering.
170	* @throws NullPointerException if the specified element is <tt>null</tt>.
171	*/
172	public boolean offer(E o) {
173	if (o == null)
174	throw new NullPointerException();
175	modCount++;
176	++size;
177
178	// Grow backing store if necessary
179	// FIXME: watch for overflow
180	// FIXME: what if we're full?
181	while (size >= queue.length) {
182	Object[] newQueue = new Object[2 * queue.length];
183	System.arraycopy(queue, 0, newQueue, 0, queue.length);
184	queue = newQueue;
185	}
186
187	queue[size] = o;
188	fixUp(size);
189	return true;
190	}
191
192	public E poll() {
193	if (size == 0)
194	return null;
195	return (E) remove(1);
196	}
197
198	public E peek() {
199	return (E) queue[1];
200	}
201
202	// Collection Methods
203
204	// these first two override just to get the throws docs
205
206	/**
207	* @throws NullPointerException if the specified element is <tt>null</tt>.
208	* @throws ClassCastException if the specified element cannot be compared
209	* with elements currently in the priority queue according
210	* to the priority queue's ordering.
211	*/
212	public boolean add(E o) {
213	return super.add(o);
214	}
215
216	/**
217	* @throws ClassCastException if any element cannot be compared
218	* with elements currently in the priority queue according
219	* to the priority queue's ordering.
220	* @throws NullPointerException if <tt>c</tt> or any element in <tt>c</tt>
221	* is <tt>null</tt>
222	*/
223	public boolean addAll(Collection<? extends E> c) {
224	return super.addAll(c);
225	}
226
227	public boolean remove(Object o) {
228	if (o == null)
229	return false;
230
231	if (comparator == null) {
232	for (int i = 1; i <= size; i++) {
233	if (((Comparable<E>)queue[i]).compareTo((E)o) == 0) {
234	remove(i);
235	return true;
236	}
237	}
238	} else {
239	for (int i = 1; i <= size; i++) {
240	if (comparator.compare((E)queue[i], (E)o) == 0) {
241	remove(i);
242	return true;
243	}
244	}
245	}
246	return false;
247	}
248
249	public Iterator<E> iterator() {
250	return new Itr();
251	}
252
253	private class Itr implements Iterator<E> {
254	/**
255	* Index (into queue array) of element to be returned by
256	* subsequent call to next.
257	*/
258	private int cursor = 1;
259
260	/**
261	* Index of element returned by most recent call to next or
262	* previous. Reset to 0 if this element is deleted by a call
263	* to remove.
264	*/
265	private int lastRet = 0;
266
267	/**
268	* The modCount value that the iterator believes that the backing
269	* List should have. If this expectation is violated, the iterator
270	* has detected concurrent modification.
271	*/
272	private int expectedModCount = modCount;
273
274	public boolean hasNext() {
275	return cursor <= size;
276	}
277
278	public E next() {
279	checkForComodification();
280	if (cursor > size)
281	throw new NoSuchElementException();
282	E result = (E) queue[cursor];
283	lastRet = cursor++;
284	return result;
285	}
286
287	public void remove() {
288	if (lastRet == 0)
289	throw new IllegalStateException();
290	checkForComodification();
291
292	PriorityQueue.this.remove(lastRet);
293	if (lastRet < cursor)
294	cursor--;
295	lastRet = 0;
296	expectedModCount = modCount;
297	}
298
299	final void checkForComodification() {
300	if (modCount != expectedModCount)
301	throw new ConcurrentModificationException();
302	}
303	}
304
305	/**
306	* Returns the number of elements in this priority queue.
307	*
308	* @return the number of elements in this priority queue.
309	*/
310	public int size() {
311	return size;
312	}
313
314	/**
315	* Remove all elements from the priority queue.
316	*/
317	public void clear() {
318	modCount++;
319
320	// Null out element references to prevent memory leak
321	for (int i=1; i<=size; i++)
322	queue[i] = null;
323
324	size = 0;
325	}
326
327	/**
328	* Removes and returns the ith element from queue. Recall
329	* that queue is one-based, so 1 <= i <= size.
330	*
331	* XXX: Could further special-case i==size, but is it worth it?
332	* XXX: Could special-case i==0, but is it worth it?
333	*/
334	private E remove(int i) {
335	assert i <= size;
336	modCount++;
337
338	E result = (E) queue[i];
339	queue[i] = queue[size];
340	queue[size--] = null; // Drop extra ref to prevent memory leak
341	if (i <= size)
342	fixDown(i);
343	return result;
344	}
345
346	/**
347	* Establishes the heap invariant (described above) assuming the heap
348	* satisfies the invariant except possibly for the leaf-node indexed by k
349	* (which may have a nextExecutionTime less than its parent's).
350	*
351	* This method functions by "promoting" queue[k] up the hierarchy
352	* (by swapping it with its parent) repeatedly until queue[k]
353	* is greater than or equal to its parent.
354	*/
355	private void fixUp(int k) {
356	if (comparator == null) {
357	while (k > 1) {
358	int j = k >> 1;
359	if (((Comparable<E>)queue[j]).compareTo((E)queue[k]) <= 0)
360	break;
361	Object tmp = queue[j]; queue[j] = queue[k]; queue[k] = tmp;
362	k = j;
363	}
364	} else {
365	while (k > 1) {
366	int j = k >> 1;
367	if (comparator.compare((E)queue[j], (E)queue[k]) <= 0)
368	break;
369	Object tmp = queue[j]; queue[j] = queue[k]; queue[k] = tmp;
370	k = j;
371	}
372	}
373	}
374
375	/**
376	* Establishes the heap invariant (described above) in the subtree
377	* rooted at k, which is assumed to satisfy the heap invariant except
378	* possibly for node k itself (which may be greater than its children).
379	*
380	* This method functions by "demoting" queue[k] down the hierarchy
381	* (by swapping it with its smaller child) repeatedly until queue[k]
382	* is less than or equal to its children.
383	*/
384	private void fixDown(int k) {
385	int j;
386	if (comparator == null) {
387	while ((j = k << 1) <= size) {
388	if (j<size && ((Comparable<E>)queue[j]).compareTo((E)queue[j+1]) > 0)
389	j++; // j indexes smallest kid
390	if (((Comparable<E>)queue[k]).compareTo((E)queue[j]) <= 0)
391	break;
392	Object tmp = queue[j]; queue[j] = queue[k]; queue[k] = tmp;
393	k = j;
394	}
395	} else {
396	while ((j = k << 1) <= size) {
397	if (j < size && comparator.compare((E)queue[j], (E)queue[j+1]) > 0)
398	j++; // j indexes smallest kid
399	if (comparator.compare((E)queue[k], (E)queue[j]) <= 0)
400	break;
401	Object tmp = queue[j]; queue[j] = queue[k]; queue[k] = tmp;
402	k = j;
403	}
404	}
405	}
406
407	public Comparator<? super E> comparator() {
408	return comparator;
409	}
410
411	/**
412	* Save the state of the instance to a stream (that
413	* is, serialize it).
414	*
415	* @serialData The length of the array backing the instance is
416	* emitted (int), followed by all of its elements (each an
417	* <tt>Object</tt>) in the proper order.
418	* @param s the stream
419	*/
420	private synchronized void writeObject(java.io.ObjectOutputStream s)
421	throws java.io.IOException{
422	// Write out element count, and any hidden stuff
423	s.defaultWriteObject();
424
425	// Write out array length
426	s.writeInt(queue.length);
427
428	// Write out all elements in the proper order.
429	for (int i=0; i<size; i++)
430	s.writeObject(queue[i]);
431	}
432
433	/**
434	* Reconstitute the <tt>ArrayList</tt> instance from a stream (that is,
435	* deserialize it).
436	* @param s the stream
437	*/
438	private synchronized void readObject(java.io.ObjectInputStream s)
439	throws java.io.IOException, ClassNotFoundException {
440	// Read in size, and any hidden stuff
441	s.defaultReadObject();
442
443	// Read in array length and allocate array
444	int arrayLength = s.readInt();
445	queue = new Object[arrayLength];
446
447	// Read in all elements in the proper order.
448	for (int i=0; i<size; i++)
449	queue[i] = s.readObject();
450	}
451
452	}
453