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