View Javadoc
1   /*
2    * Copyright (c) 2003, 2013, Oracle and/or its affiliates. All rights reserved.
3    * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4    *
5    * This code is free software; you can redistribute it and/or modify it
6    * under the terms of the GNU General Public License version 2 only, as
7    * published by the Free Software Foundation.  Oracle designates this
8    * particular file as subject to the "Classpath" exception as provided
9    * by Oracle in the LICENSE file that accompanied this code.
10   *
11   * This code is distributed in the hope that it will be useful, but WITHOUT
12   * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13   * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
14   * version 2 for more details (a copy is included in the LICENSE file that
15   * accompanied this code).
16   *
17   * You should have received a copy of the GNU General Public License version
18   * 2 along with this work; if not, write to the Free Software Foundation,
19   * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20   *
21   * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22   * or visit www.oracle.com if you need additional information or have any
23   * questions.
24   */
25  
26  package java.util;
27  
28  import java.util.function.Consumer;
29  
30  /**
31   * An unbounded priority {@linkplain Queue queue} based on a priority heap.
32   * The elements of the priority queue are ordered according to their
33   * {@linkplain Comparable natural ordering}, or by a {@link Comparator}
34   * provided at queue construction time, depending on which constructor is
35   * used.  A priority queue does not permit {@code null} elements.
36   * A priority queue relying on natural ordering also does not permit
37   * insertion of non-comparable objects (doing so may result in
38   * {@code ClassCastException}).
39   *
40   * <p>The <em>head</em> of this queue is the <em>least</em> element
41   * with respect to the specified ordering.  If multiple elements are
42   * tied for least value, the head is one of those elements -- ties are
43   * broken arbitrarily.  The queue retrieval operations {@code poll},
44   * {@code remove}, {@code peek}, and {@code element} access the
45   * element at the head of the queue.
46   *
47   * <p>A priority queue is unbounded, but has an internal
48   * <i>capacity</i> governing the size of an array used to store the
49   * elements on the queue.  It is always at least as large as the queue
50   * size.  As elements are added to a priority queue, its capacity
51   * grows automatically.  The details of the growth policy are not
52   * specified.
53   *
54   * <p>This class and its iterator implement all of the
55   * <em>optional</em> methods of the {@link Collection} and {@link
56   * Iterator} interfaces.  The Iterator provided in method {@link
57   * #iterator()} is <em>not</em> guaranteed to traverse the elements of
58   * the priority queue in any particular order. If you need ordered
59   * traversal, consider using {@code Arrays.sort(pq.toArray())}.
60   *
61   * <p><strong>Note that this implementation is not synchronized.</strong>
62   * Multiple threads should not access a {@code PriorityQueue}
63   * instance concurrently if any of the threads modifies the queue.
64   * Instead, use the thread-safe {@link
65   * java.util.concurrent.PriorityBlockingQueue} class.
66   *
67   * <p>Implementation note: this implementation provides
68   * O(log(n)) time for the enqueuing and dequeuing methods
69   * ({@code offer}, {@code poll}, {@code remove()} and {@code add});
70   * linear time for the {@code remove(Object)} and {@code contains(Object)}
71   * methods; and constant time for the retrieval methods
72   * ({@code peek}, {@code element}, and {@code size}).
73   *
74   * <p>This class is a member of the
75   * <a href="{@docRoot}/../technotes/guides/collections/index.html">
76   * Java Collections Framework</a>.
77   *
78   * @since 1.5
79   * @author Josh Bloch, Doug Lea
80   * @param <E> the type of elements held in this collection
81   */
82  public class PriorityQueue<E> extends AbstractQueue<E>
83      implements java.io.Serializable {
84  
85      private static final long serialVersionUID = -7720805057305804111L;
86  
87      private static final int DEFAULT_INITIAL_CAPACITY = 11;
88  
89      /**
90       * Priority queue represented as a balanced binary heap: the two
91       * children of queue[n] are queue[2*n+1] and queue[2*(n+1)].  The
92       * priority queue is ordered by comparator, or by the elements'
93       * natural ordering, if comparator is null: For each node n in the
94       * heap and each descendant d of n, n <= d.  The element with the
95       * lowest value is in queue[0], assuming the queue is nonempty.
96       */
97      transient Object[] queue; // non-private to simplify nested class access
98  
99      /**
100      * The number of elements in the priority queue.
101      */
102     private int size = 0;
103 
104     /**
105      * The comparator, or null if priority queue uses elements'
106      * natural ordering.
107      */
108     private final Comparator<? super E> comparator;
109 
110     /**
111      * The number of times this priority queue has been
112      * <i>structurally modified</i>.  See AbstractList for gory details.
113      */
114     transient int modCount = 0; // non-private to simplify nested class access
115 
116     /**
117      * Creates a {@code PriorityQueue} with the default initial
118      * capacity (11) that orders its elements according to their
119      * {@linkplain Comparable natural ordering}.
120      */
121     public PriorityQueue() {
122         this(DEFAULT_INITIAL_CAPACITY, null);
123     }
124 
125     /**
126      * Creates a {@code PriorityQueue} with the specified initial
127      * capacity that orders its elements according to their
128      * {@linkplain Comparable natural ordering}.
129      *
130      * @param initialCapacity the initial capacity for this priority queue
131      * @throws IllegalArgumentException if {@code initialCapacity} is less
132      *         than 1
133      */
134     public PriorityQueue(int initialCapacity) {
135         this(initialCapacity, null);
136     }
137 
138     /**
139      * Creates a {@code PriorityQueue} with the default initial capacity and
140      * whose elements are ordered according to the specified comparator.
141      *
142      * @param  comparator the comparator that will be used to order this
143      *         priority queue.  If {@code null}, the {@linkplain Comparable
144      *         natural ordering} of the elements will be used.
145      * @since 1.8
146      */
147     public PriorityQueue(Comparator<? super E> comparator) {
148         this(DEFAULT_INITIAL_CAPACITY, comparator);
149     }
150 
151     /**
152      * Creates a {@code PriorityQueue} with the specified initial capacity
153      * that orders its elements according to the specified comparator.
154      *
155      * @param  initialCapacity the initial capacity for this priority queue
156      * @param  comparator the comparator that will be used to order this
157      *         priority queue.  If {@code null}, the {@linkplain Comparable
158      *         natural ordering} of the elements will be used.
159      * @throws IllegalArgumentException if {@code initialCapacity} is
160      *         less than 1
161      */
162     public PriorityQueue(int initialCapacity,
163                          Comparator<? super E> comparator) {
164         // Note: This restriction of at least one is not actually needed,
165         // but continues for 1.5 compatibility
166         if (initialCapacity < 1)
167             throw new IllegalArgumentException();
168         this.queue = new Object[initialCapacity];
169         this.comparator = comparator;
170     }
171 
172     /**
173      * Creates a {@code PriorityQueue} containing the elements in the
174      * specified collection.  If the specified collection is an instance of
175      * a {@link SortedSet} or is another {@code PriorityQueue}, this
176      * priority queue will be ordered according to the same ordering.
177      * Otherwise, this priority queue will be ordered according to the
178      * {@linkplain Comparable natural ordering} of its elements.
179      *
180      * @param  c the collection whose elements are to be placed
181      *         into this priority queue
182      * @throws ClassCastException if elements of the specified collection
183      *         cannot be compared to one another according to the priority
184      *         queue's ordering
185      * @throws NullPointerException if the specified collection or any
186      *         of its elements are null
187      */
188     @SuppressWarnings("unchecked")
189     public PriorityQueue(Collection<? extends E> c) {
190         if (c instanceof SortedSet<?>) {
191             SortedSet<? extends E> ss = (SortedSet<? extends E>) c;
192             this.comparator = (Comparator<? super E>) ss.comparator();
193             initElementsFromCollection(ss);
194         }
195         else if (c instanceof PriorityQueue<?>) {
196             PriorityQueue<? extends E> pq = (PriorityQueue<? extends E>) c;
197             this.comparator = (Comparator<? super E>) pq.comparator();
198             initFromPriorityQueue(pq);
199         }
200         else {
201             this.comparator = null;
202             initFromCollection(c);
203         }
204     }
205 
206     /**
207      * Creates a {@code PriorityQueue} containing the elements in the
208      * specified priority queue.  This priority queue will be
209      * ordered according to the same ordering as the given priority
210      * queue.
211      *
212      * @param  c the priority queue whose elements are to be placed
213      *         into this priority queue
214      * @throws ClassCastException if elements of {@code c} cannot be
215      *         compared to one another according to {@code c}'s
216      *         ordering
217      * @throws NullPointerException if the specified priority queue or any
218      *         of its elements are null
219      */
220     @SuppressWarnings("unchecked")
221     public PriorityQueue(PriorityQueue<? extends E> c) {
222         this.comparator = (Comparator<? super E>) c.comparator();
223         initFromPriorityQueue(c);
224     }
225 
226     /**
227      * Creates a {@code PriorityQueue} containing the elements in the
228      * specified sorted set.   This priority queue will be ordered
229      * according to the same ordering as the given sorted set.
230      *
231      * @param  c the sorted set whose elements are to be placed
232      *         into this priority queue
233      * @throws ClassCastException if elements of the specified sorted
234      *         set cannot be compared to one another according to the
235      *         sorted set's ordering
236      * @throws NullPointerException if the specified sorted set or any
237      *         of its elements are null
238      */
239     @SuppressWarnings("unchecked")
240     public PriorityQueue(SortedSet<? extends E> c) {
241         this.comparator = (Comparator<? super E>) c.comparator();
242         initElementsFromCollection(c);
243     }
244 
245     private void initFromPriorityQueue(PriorityQueue<? extends E> c) {
246         if (c.getClass() == PriorityQueue.class) {
247             this.queue = c.toArray();
248             this.size = c.size();
249         } else {
250             initFromCollection(c);
251         }
252     }
253 
254     private void initElementsFromCollection(Collection<? extends E> c) {
255         Object[] a = c.toArray();
256         // If c.toArray incorrectly doesn't return Object[], copy it.
257         if (a.getClass() != Object[].class)
258             a = Arrays.copyOf(a, a.length, Object[].class);
259         int len = a.length;
260         if (len == 1 || this.comparator != null)
261             for (int i = 0; i < len; i++)
262                 if (a[i] == null)
263                     throw new NullPointerException();
264         this.queue = a;
265         this.size = a.length;
266     }
267 
268     /**
269      * Initializes queue array with elements from the given Collection.
270      *
271      * @param c the collection
272      */
273     private void initFromCollection(Collection<? extends E> c) {
274         initElementsFromCollection(c);
275         heapify();
276     }
277 
278     /**
279      * The maximum size of array to allocate.
280      * Some VMs reserve some header words in an array.
281      * Attempts to allocate larger arrays may result in
282      * OutOfMemoryError: Requested array size exceeds VM limit
283      */
284     private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
285 
286     /**
287      * Increases the capacity of the array.
288      *
289      * @param minCapacity the desired minimum capacity
290      */
291     private void grow(int minCapacity) {
292         int oldCapacity = queue.length;
293         // Double size if small; else grow by 50%
294         int newCapacity = oldCapacity + ((oldCapacity < 64) ?
295                                          (oldCapacity + 2) :
296                                          (oldCapacity >> 1));
297         // overflow-conscious code
298         if (newCapacity - MAX_ARRAY_SIZE > 0)
299             newCapacity = hugeCapacity(minCapacity);
300         queue = Arrays.copyOf(queue, newCapacity);
301     }
302 
303     private static int hugeCapacity(int minCapacity) {
304         if (minCapacity < 0) // overflow
305             throw new OutOfMemoryError();
306         return (minCapacity > MAX_ARRAY_SIZE) ?
307             Integer.MAX_VALUE :
308             MAX_ARRAY_SIZE;
309     }
310 
311     /**
312      * Inserts the specified element into this priority queue.
313      *
314      * @return {@code true} (as specified by {@link Collection#add})
315      * @throws ClassCastException if the specified element cannot be
316      *         compared with elements currently in this priority queue
317      *         according to the priority queue's ordering
318      * @throws NullPointerException if the specified element is null
319      */
320     public boolean add(E e) {
321         return offer(e);
322     }
323 
324     /**
325      * Inserts the specified element into this priority queue.
326      *
327      * @return {@code true} (as specified by {@link Queue#offer})
328      * @throws ClassCastException if the specified element cannot be
329      *         compared with elements currently in this priority queue
330      *         according to the priority queue's ordering
331      * @throws NullPointerException if the specified element is null
332      */
333     public boolean offer(E e) {
334         if (e == null)
335             throw new NullPointerException();
336         modCount++;
337         int i = size;
338         if (i >= queue.length)
339             grow(i + 1);
340         size = i + 1;
341         if (i == 0)
342             queue[0] = e;
343         else
344             siftUp(i, e);
345         return true;
346     }
347 
348     @SuppressWarnings("unchecked")
349     public E peek() {
350         return (size == 0) ? null : (E) queue[0];
351     }
352 
353     private int indexOf(Object o) {
354         if (o != null) {
355             for (int i = 0; i < size; i++)
356                 if (o.equals(queue[i]))
357                     return i;
358         }
359         return -1;
360     }
361 
362     /**
363      * Removes a single instance of the specified element from this queue,
364      * if it is present.  More formally, removes an element {@code e} such
365      * that {@code o.equals(e)}, if this queue contains one or more such
366      * elements.  Returns {@code true} if and only if this queue contained
367      * the specified element (or equivalently, if this queue changed as a
368      * result of the call).
369      *
370      * @param o element to be removed from this queue, if present
371      * @return {@code true} if this queue changed as a result of the call
372      */
373     public boolean remove(Object o) {
374         int i = indexOf(o);
375         if (i == -1)
376             return false;
377         else {
378             removeAt(i);
379             return true;
380         }
381     }
382 
383     /**
384      * Version of remove using reference equality, not equals.
385      * Needed by iterator.remove.
386      *
387      * @param o element to be removed from this queue, if present
388      * @return {@code true} if removed
389      */
390     boolean removeEq(Object o) {
391         for (int i = 0; i < size; i++) {
392             if (o == queue[i]) {
393                 removeAt(i);
394                 return true;
395             }
396         }
397         return false;
398     }
399 
400     /**
401      * Returns {@code true} if this queue contains the specified element.
402      * More formally, returns {@code true} if and only if this queue contains
403      * at least one element {@code e} such that {@code o.equals(e)}.
404      *
405      * @param o object to be checked for containment in this queue
406      * @return {@code true} if this queue contains the specified element
407      */
408     public boolean contains(Object o) {
409         return indexOf(o) != -1;
410     }
411 
412     /**
413      * Returns an array containing all of the elements in this queue.
414      * The elements are in no particular order.
415      *
416      * <p>The returned array will be "safe" in that no references to it are
417      * maintained by this queue.  (In other words, this method must allocate
418      * a new array).  The caller is thus free to modify the returned array.
419      *
420      * <p>This method acts as bridge between array-based and collection-based
421      * APIs.
422      *
423      * @return an array containing all of the elements in this queue
424      */
425     public Object[] toArray() {
426         return Arrays.copyOf(queue, size);
427     }
428 
429     /**
430      * Returns an array containing all of the elements in this queue; the
431      * runtime type of the returned array is that of the specified array.
432      * The returned array elements are in no particular order.
433      * If the queue fits in the specified array, it is returned therein.
434      * Otherwise, a new array is allocated with the runtime type of the
435      * specified array and the size of this queue.
436      *
437      * <p>If the queue fits in the specified array with room to spare
438      * (i.e., the array has more elements than the queue), the element in
439      * the array immediately following the end of the collection is set to
440      * {@code null}.
441      *
442      * <p>Like the {@link #toArray()} method, this method acts as bridge between
443      * array-based and collection-based APIs.  Further, this method allows
444      * precise control over the runtime type of the output array, and may,
445      * under certain circumstances, be used to save allocation costs.
446      *
447      * <p>Suppose {@code x} is a queue known to contain only strings.
448      * The following code can be used to dump the queue into a newly
449      * allocated array of {@code String}:
450      *
451      *  <pre> {@code String[] y = x.toArray(new String[0]);}</pre>
452      *
453      * Note that {@code toArray(new Object[0])} is identical in function to
454      * {@code toArray()}.
455      *
456      * @param a the array into which the elements of the queue are to
457      *          be stored, if it is big enough; otherwise, a new array of the
458      *          same runtime type is allocated for this purpose.
459      * @return an array containing all of the elements in this queue
460      * @throws ArrayStoreException if the runtime type of the specified array
461      *         is not a supertype of the runtime type of every element in
462      *         this queue
463      * @throws NullPointerException if the specified array is null
464      */
465     @SuppressWarnings("unchecked")
466     public <T> T[] toArray(T[] a) {
467         final int size = this.size;
468         if (a.length < size)
469             // Make a new array of a's runtime type, but my contents:
470             return (T[]) Arrays.copyOf(queue, size, a.getClass());
471         System.arraycopy(queue, 0, a, 0, size);
472         if (a.length > size)
473             a[size] = null;
474         return a;
475     }
476 
477     /**
478      * Returns an iterator over the elements in this queue. The iterator
479      * does not return the elements in any particular order.
480      *
481      * @return an iterator over the elements in this queue
482      */
483     public Iterator<E> iterator() {
484         return new Itr();
485     }
486 
487     private final class Itr implements Iterator<E> {
488         /**
489          * Index (into queue array) of element to be returned by
490          * subsequent call to next.
491          */
492         private int cursor = 0;
493 
494         /**
495          * Index of element returned by most recent call to next,
496          * unless that element came from the forgetMeNot list.
497          * Set to -1 if element is deleted by a call to remove.
498          */
499         private int lastRet = -1;
500 
501         /**
502          * A queue of elements that were moved from the unvisited portion of
503          * the heap into the visited portion as a result of "unlucky" element
504          * removals during the iteration.  (Unlucky element removals are those
505          * that require a siftup instead of a siftdown.)  We must visit all of
506          * the elements in this list to complete the iteration.  We do this
507          * after we've completed the "normal" iteration.
508          *
509          * We expect that most iterations, even those involving removals,
510          * will not need to store elements in this field.
511          */
512         private ArrayDeque<E> forgetMeNot = null;
513 
514         /**
515          * Element returned by the most recent call to next iff that
516          * element was drawn from the forgetMeNot list.
517          */
518         private E lastRetElt = null;
519 
520         /**
521          * The modCount value that the iterator believes that the backing
522          * Queue should have.  If this expectation is violated, the iterator
523          * has detected concurrent modification.
524          */
525         private int expectedModCount = modCount;
526 
527         public boolean hasNext() {
528             return cursor < size ||
529                 (forgetMeNot != null && !forgetMeNot.isEmpty());
530         }
531 
532         @SuppressWarnings("unchecked")
533         public E next() {
534             if (expectedModCount != modCount)
535                 throw new ConcurrentModificationException();
536             if (cursor < size)
537                 return (E) queue[lastRet = cursor++];
538             if (forgetMeNot != null) {
539                 lastRet = -1;
540                 lastRetElt = forgetMeNot.poll();
541                 if (lastRetElt != null)
542                     return lastRetElt;
543             }
544             throw new NoSuchElementException();
545         }
546 
547         public void remove() {
548             if (expectedModCount != modCount)
549                 throw new ConcurrentModificationException();
550             if (lastRet != -1) {
551                 E moved = PriorityQueue.this.removeAt(lastRet);
552                 lastRet = -1;
553                 if (moved == null)
554                     cursor--;
555                 else {
556                     if (forgetMeNot == null)
557                         forgetMeNot = new ArrayDeque<>();
558                     forgetMeNot.add(moved);
559                 }
560             } else if (lastRetElt != null) {
561                 PriorityQueue.this.removeEq(lastRetElt);
562                 lastRetElt = null;
563             } else {
564                 throw new IllegalStateException();
565             }
566             expectedModCount = modCount;
567         }
568     }
569 
570     public int size() {
571         return size;
572     }
573 
574     /**
575      * Removes all of the elements from this priority queue.
576      * The queue will be empty after this call returns.
577      */
578     public void clear() {
579         modCount++;
580         for (int i = 0; i < size; i++)
581             queue[i] = null;
582         size = 0;
583     }
584 
585     @SuppressWarnings("unchecked")
586     public E poll() {
587         if (size == 0)
588             return null;
589         int s = --size;
590         modCount++;
591         E result = (E) queue[0];
592         E x = (E) queue[s];
593         queue[s] = null;
594         if (s != 0)
595             siftDown(0, x);
596         return result;
597     }
598 
599     /**
600      * Removes the ith element from queue.
601      *
602      * Normally this method leaves the elements at up to i-1,
603      * inclusive, untouched.  Under these circumstances, it returns
604      * null.  Occasionally, in order to maintain the heap invariant,
605      * it must swap a later element of the list with one earlier than
606      * i.  Under these circumstances, this method returns the element
607      * that was previously at the end of the list and is now at some
608      * position before i. This fact is used by iterator.remove so as to
609      * avoid missing traversing elements.
610      */
611     @SuppressWarnings("unchecked")
612     private E removeAt(int i) {
613         // assert i >= 0 && i < size;
614         modCount++;
615         int s = --size;
616         if (s == i) // removed last element
617             queue[i] = null;
618         else {
619             E moved = (E) queue[s];
620             queue[s] = null;
621             siftDown(i, moved);
622             if (queue[i] == moved) {
623                 siftUp(i, moved);
624                 if (queue[i] != moved)
625                     return moved;
626             }
627         }
628         return null;
629     }
630 
631     /**
632      * Inserts item x at position k, maintaining heap invariant by
633      * promoting x up the tree until it is greater than or equal to
634      * its parent, or is the root.
635      *
636      * To simplify and speed up coercions and comparisons. the
637      * Comparable and Comparator versions are separated into different
638      * methods that are otherwise identical. (Similarly for siftDown.)
639      *
640      * @param k the position to fill
641      * @param x the item to insert
642      */
643     private void siftUp(int k, E x) {
644         if (comparator != null)
645             siftUpUsingComparator(k, x);
646         else
647             siftUpComparable(k, x);
648     }
649 
650     @SuppressWarnings("unchecked")
651     private void siftUpComparable(int k, E x) {
652         Comparable<? super E> key = (Comparable<? super E>) x;
653         while (k > 0) {
654             int parent = (k - 1) >>> 1;
655             Object e = queue[parent];
656             if (key.compareTo((E) e) >= 0)
657                 break;
658             queue[k] = e;
659             k = parent;
660         }
661         queue[k] = key;
662     }
663 
664     @SuppressWarnings("unchecked")
665     private void siftUpUsingComparator(int k, E x) {
666         while (k > 0) {
667             int parent = (k - 1) >>> 1;
668             Object e = queue[parent];
669             if (comparator.compare(x, (E) e) >= 0)
670                 break;
671             queue[k] = e;
672             k = parent;
673         }
674         queue[k] = x;
675     }
676 
677     /**
678      * Inserts item x at position k, maintaining heap invariant by
679      * demoting x down the tree repeatedly until it is less than or
680      * equal to its children or is a leaf.
681      *
682      * @param k the position to fill
683      * @param x the item to insert
684      */
685     private void siftDown(int k, E x) {
686         if (comparator != null)
687             siftDownUsingComparator(k, x);
688         else
689             siftDownComparable(k, x);
690     }
691 
692     @SuppressWarnings("unchecked")
693     private void siftDownComparable(int k, E x) {
694         Comparable<? super E> key = (Comparable<? super E>)x;
695         int half = size >>> 1;        // loop while a non-leaf
696         while (k < half) {
697             int child = (k << 1) + 1; // assume left child is least
698             Object c = queue[child];
699             int right = child + 1;
700             if (right < size &&
701                 ((Comparable<? super E>) c).compareTo((E) queue[right]) > 0)
702                 c = queue[child = right];
703             if (key.compareTo((E) c) <= 0)
704                 break;
705             queue[k] = c;
706             k = child;
707         }
708         queue[k] = key;
709     }
710 
711     @SuppressWarnings("unchecked")
712     private void siftDownUsingComparator(int k, E x) {
713         int half = size >>> 1;
714         while (k < half) {
715             int child = (k << 1) + 1;
716             Object c = queue[child];
717             int right = child + 1;
718             if (right < size &&
719                 comparator.compare((E) c, (E) queue[right]) > 0)
720                 c = queue[child = right];
721             if (comparator.compare(x, (E) c) <= 0)
722                 break;
723             queue[k] = c;
724             k = child;
725         }
726         queue[k] = x;
727     }
728 
729     /**
730      * Establishes the heap invariant (described above) in the entire tree,
731      * assuming nothing about the order of the elements prior to the call.
732      */
733     @SuppressWarnings("unchecked")
734     private void heapify() {
735         for (int i = (size >>> 1) - 1; i >= 0; i--)
736             siftDown(i, (E) queue[i]);
737     }
738 
739     /**
740      * Returns the comparator used to order the elements in this
741      * queue, or {@code null} if this queue is sorted according to
742      * the {@linkplain Comparable natural ordering} of its elements.
743      *
744      * @return the comparator used to order this queue, or
745      *         {@code null} if this queue is sorted according to the
746      *         natural ordering of its elements
747      */
748     public Comparator<? super E> comparator() {
749         return comparator;
750     }
751 
752     /**
753      * Saves this queue to a stream (that is, serializes it).
754      *
755      * @serialData The length of the array backing the instance is
756      *             emitted (int), followed by all of its elements
757      *             (each an {@code Object}) in the proper order.
758      * @param s the stream
759      */
760     private void writeObject(java.io.ObjectOutputStream s)
761         throws java.io.IOException {
762         // Write out element count, and any hidden stuff
763         s.defaultWriteObject();
764 
765         // Write out array length, for compatibility with 1.5 version
766         s.writeInt(Math.max(2, size + 1));
767 
768         // Write out all elements in the "proper order".
769         for (int i = 0; i < size; i++)
770             s.writeObject(queue[i]);
771     }
772 
773     /**
774      * Reconstitutes the {@code PriorityQueue} instance from a stream
775      * (that is, deserializes it).
776      *
777      * @param s the stream
778      */
779     private void readObject(java.io.ObjectInputStream s)
780         throws java.io.IOException, ClassNotFoundException {
781         // Read in size, and any hidden stuff
782         s.defaultReadObject();
783 
784         // Read in (and discard) array length
785         s.readInt();
786 
787         queue = new Object[size];
788 
789         // Read in all elements.
790         for (int i = 0; i < size; i++)
791             queue[i] = s.readObject();
792 
793         // Elements are guaranteed to be in "proper order", but the
794         // spec has never explained what that might be.
795         heapify();
796     }
797 
798     /**
799      * Creates a <em><a href="Spliterator.html#binding">late-binding</a></em>
800      * and <em>fail-fast</em> {@link Spliterator} over the elements in this
801      * queue.
802      *
803      * <p>The {@code Spliterator} reports {@link Spliterator#SIZED},
804      * {@link Spliterator#SUBSIZED}, and {@link Spliterator#NONNULL}.
805      * Overriding implementations should document the reporting of additional
806      * characteristic values.
807      *
808      * @return a {@code Spliterator} over the elements in this queue
809      * @since 1.8
810      */
811     public final Spliterator<E> spliterator() {
812         return new PriorityQueueSpliterator<E>(this, 0, -1, 0);
813     }
814 
815     static final class PriorityQueueSpliterator<E> implements Spliterator<E> {
816         /*
817          * This is very similar to ArrayList Spliterator, except for
818          * extra null checks.
819          */
820         private final PriorityQueue<E> pq;
821         private int index;            // current index, modified on advance/split
822         private int fence;            // -1 until first use
823         private int expectedModCount; // initialized when fence set
824 
825         /** Creates new spliterator covering the given range */
826         PriorityQueueSpliterator(PriorityQueue<E> pq, int origin, int fence,
827                              int expectedModCount) {
828             this.pq = pq;
829             this.index = origin;
830             this.fence = fence;
831             this.expectedModCount = expectedModCount;
832         }
833 
834         private int getFence() { // initialize fence to size on first use
835             int hi;
836             if ((hi = fence) < 0) {
837                 expectedModCount = pq.modCount;
838                 hi = fence = pq.size;
839             }
840             return hi;
841         }
842 
843         public PriorityQueueSpliterator<E> trySplit() {
844             int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
845             return (lo >= mid) ? null :
846                 new PriorityQueueSpliterator<E>(pq, lo, index = mid,
847                                                 expectedModCount);
848         }
849 
850         @SuppressWarnings("unchecked")
851         public void forEachRemaining(Consumer<? super E> action) {
852             int i, hi, mc; // hoist accesses and checks from loop
853             PriorityQueue<E> q; Object[] a;
854             if (action == null)
855                 throw new NullPointerException();
856             if ((q = pq) != null && (a = q.queue) != null) {
857                 if ((hi = fence) < 0) {
858                     mc = q.modCount;
859                     hi = q.size;
860                 }
861                 else
862                     mc = expectedModCount;
863                 if ((i = index) >= 0 && (index = hi) <= a.length) {
864                     for (E e;; ++i) {
865                         if (i < hi) {
866                             if ((e = (E) a[i]) == null) // must be CME
867                                 break;
868                             action.accept(e);
869                         }
870                         else if (q.modCount != mc)
871                             break;
872                         else
873                             return;
874                     }
875                 }
876             }
877             throw new ConcurrentModificationException();
878         }
879 
880         public boolean tryAdvance(Consumer<? super E> action) {
881             if (action == null)
882                 throw new NullPointerException();
883             int hi = getFence(), lo = index;
884             if (lo >= 0 && lo < hi) {
885                 index = lo + 1;
886                 @SuppressWarnings("unchecked") E e = (E)pq.queue[lo];
887                 if (e == null)
888                     throw new ConcurrentModificationException();
889                 action.accept(e);
890                 if (pq.modCount != expectedModCount)
891                     throw new ConcurrentModificationException();
892                 return true;
893             }
894             return false;
895         }
896 
897         public long estimateSize() {
898             return (long) (getFence() - index);
899         }
900 
901         public int characteristics() {
902             return Spliterator.SIZED | Spliterator.SUBSIZED | Spliterator.NONNULL;
903         }
904     }
905 }