1 /*
   2  * Copyright (c) 2003, 2010, 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 /**
  29  * An unbounded priority {@linkplain Queue queue} based on a priority heap.
  30  * The elements of the priority queue are ordered according to their
  31  * {@linkplain Comparable natural ordering}, or by a {@link Comparator}
  32  * provided at queue construction time, depending on which constructor is
  33  * used.  A priority queue does not permit {@code null} elements.
  34  * A priority queue relying on natural ordering also does not permit
  35  * insertion of non-comparable objects (doing so may result in
  36  * {@code ClassCastException}).
  37  *
  38  * <p>The <em>head</em> of this queue is the <em>least</em> element
  39  * with respect to the specified ordering.  If multiple elements are
  40  * tied for least value, the head is one of those elements -- ties are
  41  * broken arbitrarily.  The queue retrieval operations {@code poll},
  42  * {@code remove}, {@code peek}, and {@code element} access the
  43  * element at the head of the queue.
  44  *
  45  * <p>A priority queue is unbounded, but has an internal
  46  * <i>capacity</i> governing the size of an array used to store the
  47  * elements on the queue.  It is always at least as large as the queue
  48  * size.  As elements are added to a priority queue, its capacity
  49  * grows automatically.  The details of the growth policy are not
  50  * specified.
  51  *
  52  * <p>This class and its iterator implement all of the
  53  * <em>optional</em> methods of the {@link Collection} and {@link
  54  * Iterator} interfaces.  The Iterator provided in method {@link
  55  * #iterator()} is <em>not</em> guaranteed to traverse the elements of
  56  * the priority queue in any particular order. If you need ordered
  57  * traversal, consider using {@code Arrays.sort(pq.toArray())}.
  58  *
  59  * <p> <strong>Note that this implementation is not synchronized.</strong>
  60  * Multiple threads should not access a {@code PriorityQueue}
  61  * instance concurrently if any of the threads modifies the queue.
  62  * Instead, use the thread-safe {@link
  63  * java.util.concurrent.PriorityBlockingQueue} class.
  64  *
  65  * <p>Implementation note: this implementation provides
  66  * O(log(n)) time for the enqueing and dequeing methods
  67  * ({@code offer}, {@code poll}, {@code remove()} and {@code add});
  68  * linear time for the {@code remove(Object)} and {@code contains(Object)}
  69  * methods; and constant time for the retrieval methods
  70  * ({@code peek}, {@code element}, and {@code size}).
  71  *
  72  * <p>This class is a member of the
  73  * <a href="{@docRoot}/../technotes/guides/collections/index.html">
  74  * Java Collections Framework</a>.
  75  *
  76  * @since 1.5
  77  * @author Josh Bloch, Doug Lea
  78  * @param <E> the type of elements held in this collection
  79  */
  80 public class PriorityQueue<E> extends AbstractQueue<E>
  81     implements java.io.Serializable {
  82 
  83     private static final long serialVersionUID = -7720805057305804111L;
  84 
  85     private static final int DEFAULT_INITIAL_CAPACITY = 11;
  86 
  87     /**
  88      * Priority queue represented as a balanced binary heap: the two
  89      * children of queue[n] are queue[2*n+1] and queue[2*(n+1)].  The
  90      * priority queue is ordered by comparator, or by the elements'
  91      * natural ordering, if comparator is null: For each node n in the
  92      * heap and each descendant d of n, n <= d.  The element with the
  93      * lowest value is in queue[0], assuming the queue is nonempty.
  94      */
  95     private transient Object[] queue;
  96 
  97     /**
  98      * The number of elements in the priority queue.
  99      */
 100     private int size = 0;
 101 
 102     /**
 103      * The comparator, or null if priority queue uses elements'
 104      * natural ordering.
 105      */
 106     private final Comparator<? super E> comparator;
 107 
 108     /**
 109      * The number of times this priority queue has been
 110      * <i>structurally modified</i>.  See AbstractList for gory details.
 111      */
 112     private transient int modCount = 0;
 113 
 114     /**
 115      * Creates a {@code PriorityQueue} with the default initial
 116      * capacity (11) that orders its elements according to their
 117      * {@linkplain Comparable natural ordering}.
 118      */
 119     public PriorityQueue() {
 120         this(DEFAULT_INITIAL_CAPACITY, null);
 121     }
 122 
 123     /**
 124      * Creates a {@code PriorityQueue} with the specified initial
 125      * capacity that orders its elements according to their
 126      * {@linkplain Comparable natural ordering}.
 127      *
 128      * @param initialCapacity the initial capacity for this priority queue
 129      * @throws IllegalArgumentException if {@code initialCapacity} is less
 130      *         than 1
 131      */
 132     public PriorityQueue(int initialCapacity) {
 133         this(initialCapacity, null);
 134     }
 135 
 136     /**
 137      * Creates a {@code PriorityQueue} with the specified initial capacity
 138      * that orders its elements according to the specified comparator.
 139      *
 140      * @param  initialCapacity the initial capacity for this priority queue
 141      * @param  comparator the comparator that will be used to order this
 142      *         priority queue.  If {@code null}, the {@linkplain Comparable
 143      *         natural ordering} of the elements will be used.
 144      * @throws IllegalArgumentException if {@code initialCapacity} is
 145      *         less than 1
 146      */
 147     public PriorityQueue(int initialCapacity,
 148                          Comparator<? super E> comparator) {
 149         // Note: This restriction of at least one is not actually needed,
 150         // but continues for 1.5 compatibility
 151         if (initialCapacity < 1)
 152             throw new IllegalArgumentException();
 153         this.queue = new Object[initialCapacity];
 154         this.comparator = comparator;
 155     }
 156 
 157     /**
 158      * Creates a {@code PriorityQueue} containing the elements in the
 159      * specified collection.  If the specified collection is an instance of
 160      * a {@link SortedSet} or is another {@code PriorityQueue}, this
 161      * priority queue will be ordered according to the same ordering.
 162      * Otherwise, this priority queue will be ordered according to the
 163      * {@linkplain Comparable natural ordering} of its elements.
 164      *
 165      * @param  c the collection whose elements are to be placed
 166      *         into this priority queue
 167      * @throws ClassCastException if elements of the specified collection
 168      *         cannot be compared to one another according to the priority
 169      *         queue's ordering
 170      * @throws NullPointerException if the specified collection or any
 171      *         of its elements are null
 172      */
 173     @SuppressWarnings("unchecked")
 174     public PriorityQueue(Collection<? extends E> c) {
 175         if (c instanceof SortedSet<?>) {
 176             SortedSet<? extends E> ss = (SortedSet<? extends E>) c;
 177             this.comparator = (Comparator<? super E>) ss.comparator();
 178             initElementsFromCollection(ss);
 179         }
 180         else if (c instanceof PriorityQueue<?>) {
 181             PriorityQueue<? extends E> pq = (PriorityQueue<? extends E>) c;
 182             this.comparator = (Comparator<? super E>) pq.comparator();
 183             initFromPriorityQueue(pq);
 184         }
 185         else {
 186             this.comparator = null;
 187             initFromCollection(c);
 188         }
 189     }
 190 
 191     /**
 192      * Creates a {@code PriorityQueue} containing the elements in the
 193      * specified priority queue.  This priority queue will be
 194      * ordered according to the same ordering as the given priority
 195      * queue.
 196      *
 197      * @param  c the priority queue whose elements are to be placed
 198      *         into this priority queue
 199      * @throws ClassCastException if elements of {@code c} cannot be
 200      *         compared to one another according to {@code c}'s
 201      *         ordering
 202      * @throws NullPointerException if the specified priority queue or any
 203      *         of its elements are null
 204      */
 205     @SuppressWarnings("unchecked")
 206     public PriorityQueue(PriorityQueue<? extends E> c) {
 207         this.comparator = (Comparator<? super E>) c.comparator();
 208         initFromPriorityQueue(c);
 209     }
 210 
 211     /**
 212      * Creates a {@code PriorityQueue} containing the elements in the
 213      * specified sorted set.   This priority queue will be ordered
 214      * according to the same ordering as the given sorted set.
 215      *
 216      * @param  c the sorted set whose elements are to be placed
 217      *         into this priority queue
 218      * @throws ClassCastException if elements of the specified sorted
 219      *         set cannot be compared to one another according to the
 220      *         sorted set's ordering
 221      * @throws NullPointerException if the specified sorted set or any
 222      *         of its elements are null
 223      */
 224     @SuppressWarnings("unchecked")
 225     public PriorityQueue(SortedSet<? extends E> c) {
 226         this.comparator = (Comparator<? super E>) c.comparator();
 227         initElementsFromCollection(c);
 228     }
 229 
 230     private void initFromPriorityQueue(PriorityQueue<? extends E> c) {
 231         if (c.getClass() == PriorityQueue.class) {
 232             this.queue = c.toArray();
 233             this.size = c.size();
 234         } else {
 235             initFromCollection(c);
 236         }
 237     }
 238 
 239     private void initElementsFromCollection(Collection<? extends E> c) {
 240         Object[] a = c.toArray();
 241         // If c.toArray incorrectly doesn't return Object[], copy it.
 242         if (a.getClass() != Object[].class)
 243             a = Arrays.copyOf(a, a.length, Object[].class);
 244         int len = a.length;
 245         if (len == 1 || this.comparator != null)
 246             for (int i = 0; i < len; i++)
 247                 if (a[i] == null)
 248                     throw new NullPointerException();
 249         this.queue = a;
 250         this.size = a.length;
 251     }
 252 
 253     /**
 254      * Initializes queue array with elements from the given Collection.
 255      *
 256      * @param c the collection
 257      */
 258     private void initFromCollection(Collection<? extends E> c) {
 259         initElementsFromCollection(c);
 260         heapify();
 261     }
 262 
 263     /**
 264      * The maximum size of array to allocate.
 265      * Some VMs reserve some header words in an array.
 266      * Attempts to allocate larger arrays may result in
 267      * OutOfMemoryError: Requested array size exceeds VM limit
 268      */
 269     private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
 270 
 271     /**
 272      * Increases the capacity of the array.
 273      *
 274      * @param minCapacity the desired minimum capacity
 275      */
 276     private void grow(int minCapacity) {
 277         int oldCapacity = queue.length;
 278         // Double size if small; else grow by 50%
 279         int newCapacity = oldCapacity + ((oldCapacity < 64) ?
 280                                          (oldCapacity + 2) :
 281                                          (oldCapacity >> 1));
 282         // overflow-conscious code
 283         if (newCapacity - MAX_ARRAY_SIZE > 0)
 284             newCapacity = hugeCapacity(minCapacity);
 285         queue = Arrays.copyOf(queue, newCapacity);
 286     }
 287 
 288     private static int hugeCapacity(int minCapacity) {
 289         if (minCapacity < 0) // overflow
 290             throw new OutOfMemoryError();
 291         return (minCapacity > MAX_ARRAY_SIZE) ?
 292             Integer.MAX_VALUE :
 293             MAX_ARRAY_SIZE;
 294     }
 295 
 296     /**
 297      * Inserts the specified element into this priority queue.
 298      *
 299      * @return {@code true} (as specified by {@link Collection#add})
 300      * @throws ClassCastException if the specified element cannot be
 301      *         compared with elements currently in this priority queue
 302      *         according to the priority queue's ordering
 303      * @throws NullPointerException if the specified element is null
 304      */
 305     public boolean add(E e) {
 306         return offer(e);
 307     }
 308 
 309     /**
 310      * Inserts the specified element into this priority queue.
 311      *
 312      * @return {@code true} (as specified by {@link Queue#offer})
 313      * @throws ClassCastException if the specified element cannot be
 314      *         compared with elements currently in this priority queue
 315      *         according to the priority queue's ordering
 316      * @throws NullPointerException if the specified element is null
 317      */
 318     public boolean offer(E e) {
 319         if (e == null)
 320             throw new NullPointerException();
 321         modCount++;
 322         int i = size;
 323         if (i >= queue.length)
 324             grow(i + 1);
 325         size = i + 1;
 326         if (i == 0)
 327             queue[0] = e;
 328         else
 329             siftUp(i, e);
 330         return true;
 331     }
 332 

 333     public E peek() {
 334         if (size == 0)
 335             return null;
 336         return (E) queue[0];
 337     }
 338 
 339     private int indexOf(Object o) {
 340         if (o != null) {
 341             for (int i = 0; i < size; i++)
 342                 if (o.equals(queue[i]))
 343                     return i;
 344         }
 345         return -1;
 346     }
 347 
 348     /**
 349      * Removes a single instance of the specified element from this queue,
 350      * if it is present.  More formally, removes an element {@code e} such
 351      * that {@code o.equals(e)}, if this queue contains one or more such
 352      * elements.  Returns {@code true} if and only if this queue contained
 353      * the specified element (or equivalently, if this queue changed as a
 354      * result of the call).
 355      *
 356      * @param o element to be removed from this queue, if present
 357      * @return {@code true} if this queue changed as a result of the call
 358      */
 359     public boolean remove(Object o) {
 360         int i = indexOf(o);
 361         if (i == -1)
 362             return false;
 363         else {
 364             removeAt(i);
 365             return true;
 366         }
 367     }
 368 
 369     /**
 370      * Version of remove using reference equality, not equals.
 371      * Needed by iterator.remove.
 372      *
 373      * @param o element to be removed from this queue, if present
 374      * @return {@code true} if removed
 375      */
 376     boolean removeEq(Object o) {
 377         for (int i = 0; i < size; i++) {
 378             if (o == queue[i]) {
 379                 removeAt(i);
 380                 return true;
 381             }
 382         }
 383         return false;
 384     }
 385 
 386     /**
 387      * Returns {@code true} if this queue contains the specified element.
 388      * More formally, returns {@code true} if and only if this queue contains
 389      * at least one element {@code e} such that {@code o.equals(e)}.
 390      *
 391      * @param o object to be checked for containment in this queue
 392      * @return {@code true} if this queue contains the specified element
 393      */
 394     public boolean contains(Object o) {
 395         return indexOf(o) != -1;
 396     }
 397 
 398     /**
 399      * Returns an array containing all of the elements in this queue.
 400      * The elements are in no particular order.
 401      *
 402      * <p>The returned array will be "safe" in that no references to it are
 403      * maintained by this queue.  (In other words, this method must allocate
 404      * a new array).  The caller is thus free to modify the returned array.
 405      *
 406      * <p>This method acts as bridge between array-based and collection-based
 407      * APIs.
 408      *
 409      * @return an array containing all of the elements in this queue
 410      */
 411     public Object[] toArray() {
 412         return Arrays.copyOf(queue, size);
 413     }
 414 
 415     /**
 416      * Returns an array containing all of the elements in this queue; the
 417      * runtime type of the returned array is that of the specified array.
 418      * The returned array elements are in no particular order.
 419      * If the queue fits in the specified array, it is returned therein.
 420      * Otherwise, a new array is allocated with the runtime type of the
 421      * specified array and the size of this queue.
 422      *
 423      * <p>If the queue fits in the specified array with room to spare
 424      * (i.e., the array has more elements than the queue), the element in
 425      * the array immediately following the end of the collection is set to
 426      * {@code null}.
 427      *
 428      * <p>Like the {@link #toArray()} method, this method acts as bridge between
 429      * array-based and collection-based APIs.  Further, this method allows
 430      * precise control over the runtime type of the output array, and may,
 431      * under certain circumstances, be used to save allocation costs.
 432      *
 433      * <p>Suppose <tt>x</tt> is a queue known to contain only strings.
 434      * The following code can be used to dump the queue into a newly
 435      * allocated array of <tt>String</tt>:
 436      *
 437      * <pre>
 438      *     String[] y = x.toArray(new String[0]);</pre>
 439      *
 440      * Note that <tt>toArray(new Object[0])</tt> is identical in function to
 441      * <tt>toArray()</tt>.
 442      *
 443      * @param a the array into which the elements of the queue are to
 444      *          be stored, if it is big enough; otherwise, a new array of the
 445      *          same runtime type is allocated for this purpose.
 446      * @return an array containing all of the elements in this queue
 447      * @throws ArrayStoreException if the runtime type of the specified array
 448      *         is not a supertype of the runtime type of every element in
 449      *         this queue
 450      * @throws NullPointerException if the specified array is null
 451      */
 452     @SuppressWarnings("unchecked")
 453     public <T> T[] toArray(T[] a) {
 454         if (a.length < size)
 455             // Make a new array of a's runtime type, but my contents:
 456             return (T[]) Arrays.copyOf(queue, size, a.getClass());
 457         System.arraycopy(queue, 0, a, 0, size);
 458         if (a.length > size)
 459             a[size] = null;
 460         return a;
 461     }
 462 
 463     /**
 464      * Returns an iterator over the elements in this queue. The iterator
 465      * does not return the elements in any particular order.
 466      *
 467      * @return an iterator over the elements in this queue
 468      */
 469     public Iterator<E> iterator() {
 470         return new Itr();
 471     }
 472 
 473     private final class Itr implements Iterator<E> {
 474         /**
 475          * Index (into queue array) of element to be returned by
 476          * subsequent call to next.
 477          */
 478         private int cursor = 0;
 479 
 480         /**
 481          * Index of element returned by most recent call to next,
 482          * unless that element came from the forgetMeNot list.
 483          * Set to -1 if element is deleted by a call to remove.
 484          */
 485         private int lastRet = -1;
 486 
 487         /**
 488          * A queue of elements that were moved from the unvisited portion of
 489          * the heap into the visited portion as a result of "unlucky" element
 490          * removals during the iteration.  (Unlucky element removals are those
 491          * that require a siftup instead of a siftdown.)  We must visit all of
 492          * the elements in this list to complete the iteration.  We do this
 493          * after we've completed the "normal" iteration.
 494          *
 495          * We expect that most iterations, even those involving removals,
 496          * will not need to store elements in this field.
 497          */
 498         private ArrayDeque<E> forgetMeNot = null;
 499 
 500         /**
 501          * Element returned by the most recent call to next iff that
 502          * element was drawn from the forgetMeNot list.
 503          */
 504         private E lastRetElt = null;
 505 
 506         /**
 507          * The modCount value that the iterator believes that the backing
 508          * Queue should have.  If this expectation is violated, the iterator
 509          * has detected concurrent modification.
 510          */
 511         private int expectedModCount = modCount;
 512 
 513         public boolean hasNext() {
 514             return cursor < size ||
 515                 (forgetMeNot != null && !forgetMeNot.isEmpty());
 516         }
 517 
 518         @SuppressWarnings("unchecked")
 519         public E next() {
 520             if (expectedModCount != modCount)
 521                 throw new ConcurrentModificationException();
 522             if (cursor < size)
 523                 return (E) queue[lastRet = cursor++];
 524             if (forgetMeNot != null) {
 525                 lastRet = -1;
 526                 lastRetElt = forgetMeNot.poll();
 527                 if (lastRetElt != null)
 528                     return lastRetElt;
 529             }
 530             throw new NoSuchElementException();
 531         }
 532 
 533         public void remove() {
 534             if (expectedModCount != modCount)
 535                 throw new ConcurrentModificationException();
 536             if (lastRet != -1) {
 537                 E moved = PriorityQueue.this.removeAt(lastRet);
 538                 lastRet = -1;
 539                 if (moved == null)
 540                     cursor--;
 541                 else {
 542                     if (forgetMeNot == null)
 543                         forgetMeNot = new ArrayDeque<>();
 544                     forgetMeNot.add(moved);
 545                 }
 546             } else if (lastRetElt != null) {
 547                 PriorityQueue.this.removeEq(lastRetElt);
 548                 lastRetElt = null;
 549             } else {
 550                 throw new IllegalStateException();
 551             }
 552             expectedModCount = modCount;
 553         }
 554     }
 555 
 556     public int size() {
 557         return size;
 558     }
 559 
 560     /**
 561      * Removes all of the elements from this priority queue.
 562      * The queue will be empty after this call returns.
 563      */
 564     public void clear() {
 565         modCount++;
 566         for (int i = 0; i < size; i++)
 567             queue[i] = null;
 568         size = 0;
 569     }
 570 
 571     public E poll() {
 572         if (size == 0)
 573             return null;
 574         int s = --size;
 575         modCount++;
 576         @SuppressWarnings("unchecked")
 577             E result = (E) queue[0];
 578         @SuppressWarnings("unchecked")
 579             E x = (E) queue[s];
 580         queue[s] = null;
 581         if (s != 0)
 582             siftDown(0, x);
 583         return result;
 584     }
 585 
 586     /**
 587      * Removes the ith element from queue.
 588      *
 589      * Normally this method leaves the elements at up to i-1,
 590      * inclusive, untouched.  Under these circumstances, it returns
 591      * null.  Occasionally, in order to maintain the heap invariant,
 592      * it must swap a later element of the list with one earlier than
 593      * i.  Under these circumstances, this method returns the element
 594      * that was previously at the end of the list and is now at some
 595      * position before i. This fact is used by iterator.remove so as to
 596      * avoid missing traversing elements.
 597      */
 598     private E removeAt(int i) {
 599         assert i >= 0 && i < size;
 600         modCount++;
 601         int s = --size;
 602         if (s == i) // removed last element
 603             queue[i] = null;
 604         else {
 605             @SuppressWarnings("unchecked")
 606                 E moved = (E) queue[s];
 607             queue[s] = null;
 608             siftDown(i, moved);
 609             if (queue[i] == moved) {
 610                 siftUp(i, moved);
 611                 if (queue[i] != moved)
 612                     return moved;
 613             }
 614         }
 615         return null;
 616     }
 617 
 618     /**
 619      * Inserts item x at position k, maintaining heap invariant by
 620      * promoting x up the tree until it is greater than or equal to
 621      * its parent, or is the root.
 622      *
 623      * To simplify and speed up coercions and comparisons. the
 624      * Comparable and Comparator versions are separated into different
 625      * methods that are otherwise identical. (Similarly for siftDown.)
 626      *
 627      * @param k the position to fill
 628      * @param x the item to insert
 629      */
 630     private void siftUp(int k, E x) {
 631         if (comparator != null)
 632             siftUpUsingComparator(k, x);
 633         else
 634             siftUpComparable(k, x);
 635     }
 636 
 637     @SuppressWarnings("unchecked")
 638     private void siftUpComparable(int k, E x) {
 639         Comparable<? super E> key = (Comparable<? super E>) x;
 640         while (k > 0) {
 641             int parent = (k - 1) >>> 1;
 642             Object e = queue[parent];
 643             if (key.compareTo((E) e) >= 0)
 644                 break;
 645             queue[k] = e;
 646             k = parent;
 647         }
 648         queue[k] = key;
 649     }
 650 
 651     private void siftUpUsingComparator(int k, E x) {
 652         while (k > 0) {
 653             int parent = (k - 1) >>> 1;
 654             @SuppressWarnings("unchecked")
 655                 E e = (E) queue[parent];
 656             if (comparator.compare(x, e) >= 0)
 657                 break;
 658             queue[k] = e;
 659             k = parent;
 660         }
 661         queue[k] = x;
 662     }
 663 
 664     /**
 665      * Inserts item x at position k, maintaining heap invariant by
 666      * demoting x down the tree repeatedly until it is less than or
 667      * equal to its children or is a leaf.
 668      *
 669      * @param k the position to fill
 670      * @param x the item to insert
 671      */
 672     private void siftDown(int k, E x) {
 673         if (comparator != null)
 674             siftDownUsingComparator(k, x);
 675         else
 676             siftDownComparable(k, x);
 677     }
 678 
 679     @SuppressWarnings("unchecked")
 680     private void siftDownComparable(int k, E x) {
 681         Comparable<? super E> key = (Comparable<? super E>)x;
 682         int half = size >>> 1;        // loop while a non-leaf
 683         while (k < half) {
 684             int child = (k << 1) + 1; // assume left child is least
 685             Object c = queue[child];
 686             int right = child + 1;
 687             if (right < size &&
 688                 ((Comparable<? super E>) c).compareTo((E) queue[right]) > 0)
 689                 c = queue[child = right];
 690             if (key.compareTo((E) c) <= 0)
 691                 break;
 692             queue[k] = c;
 693             k = child;
 694         }
 695         queue[k] = key;
 696     }
 697 
 698     @SuppressWarnings("unchecked")
 699     private void siftDownUsingComparator(int k, E x) {
 700         int half = size >>> 1;
 701         while (k < half) {
 702             int child = (k << 1) + 1;
 703             Object c = queue[child];
 704             int right = child + 1;
 705             if (right < size &&
 706                 comparator.compare((E) c, (E) queue[right]) > 0)
 707                 c = queue[child = right];
 708             if (comparator.compare(x, (E) c) <= 0)
 709                 break;
 710             queue[k] = c;
 711             k = child;
 712         }
 713         queue[k] = x;
 714     }
 715 
 716     /**
 717      * Establishes the heap invariant (described above) in the entire tree,
 718      * assuming nothing about the order of the elements prior to the call.
 719      */
 720     @SuppressWarnings("unchecked")
 721     private void heapify() {
 722         for (int i = (size >>> 1) - 1; i >= 0; i--)
 723             siftDown(i, (E) queue[i]);
 724     }
 725 
 726     /**
 727      * Returns the comparator used to order the elements in this
 728      * queue, or {@code null} if this queue is sorted according to
 729      * the {@linkplain Comparable natural ordering} of its elements.
 730      *
 731      * @return the comparator used to order this queue, or
 732      *         {@code null} if this queue is sorted according to the
 733      *         natural ordering of its elements
 734      */
 735     public Comparator<? super E> comparator() {
 736         return comparator;
 737     }
 738 
 739     /**
 740      * Saves the state of the instance to a stream (that
 741      * is, serializes it).
 742      *
 743      * @serialData The length of the array backing the instance is
 744      *             emitted (int), followed by all of its elements
 745      *             (each an {@code Object}) in the proper order.
 746      * @param s the stream
 747      */
 748     private void writeObject(java.io.ObjectOutputStream s)
 749         throws java.io.IOException{
 750         // Write out element count, and any hidden stuff
 751         s.defaultWriteObject();
 752 
 753         // Write out array length, for compatibility with 1.5 version
 754         s.writeInt(Math.max(2, size + 1));
 755 
 756         // Write out all elements in the "proper order".
 757         for (int i = 0; i < size; i++)
 758             s.writeObject(queue[i]);
 759     }
 760 
 761     /**
 762      * Reconstitutes the {@code PriorityQueue} instance from a stream
 763      * (that is, deserializes it).
 764      *
 765      * @param s the stream
 766      */
 767     private void readObject(java.io.ObjectInputStream s)
 768         throws java.io.IOException, ClassNotFoundException {
 769         // Read in size, and any hidden stuff
 770         s.defaultReadObject();
 771 
 772         // Read in (and discard) array length
 773         s.readInt();
 774 
 775         queue = new Object[size];
 776 
 777         // Read in all elements.
 778         for (int i = 0; i < size; i++)
 779             queue[i] = s.readObject();
 780 
 781         // Elements are guaranteed to be in "proper order", but the
 782         // spec has never explained what that might be.
 783         heapify();
 784     }
 785 }
--- EOF ---