--- jsr166/src/main/java/util/PriorityQueue.java	2016/08/24 21:46:18	1.110
+++ jsr166/src/main/java/util/PriorityQueue.java	2016/11/30 18:12:52	1.114
@@ -54,7 +54,8 @@ import java.util.function.Consumer;
  * <p>This class and its iterator implement all of the
  * <em>optional</em> methods of the {@link Collection} and {@link
  * Iterator} interfaces.  The Iterator provided in method {@link
- * #iterator()} is <em>not</em> guaranteed to traverse the elements of
+ * #iterator()} and the Spliterator provided in method {@link #spliterator()}
+ * are <em>not</em> guaranteed to traverse the elements of
  * the priority queue in any particular order. If you need ordered
  * traversal, consider using {@code Arrays.sort(pq.toArray())}.
  *
@@ -726,11 +727,18 @@ public class PriorityQueue<E> extends Ab
     /**
      * Establishes the heap invariant (described above) in the entire tree,
      * assuming nothing about the order of the elements prior to the call.
+     * This classic algorithm due to Floyd (1964) is known to be O(size).
      */
     @SuppressWarnings("unchecked")
     private void heapify() {
-        for (int i = (size >>> 1) - 1; i >= 0; i--)
-            siftDown(i, (E) queue[i]);
+        final Object[] es = queue;
+        final int half = (size >>> 1) - 1;
+        if (comparator == null)
+            for (int i = half; i >= 0; i--)
+                siftDownComparable(i, (E) es[i]);
+        else
+            for (int i = half; i >= 0; i--)
+                siftDownUsingComparator(i, (E) es[i]);
     }
 
     /**
@@ -799,7 +807,8 @@ public class PriorityQueue<E> extends Ab
     /**
      * Creates a <em><a href="Spliterator.html#binding">late-binding</a></em>
      * and <em>fail-fast</em> {@link Spliterator} over the elements in this
-     * queue.
+     * queue. The spliterator does not traverse elements in any particular order
+     * (the {@link Spliterator#ORDERED ORDERED} characteristic is not reported).
      *
      * <p>The {@code Spliterator} reports {@link Spliterator#SIZED},
      * {@link Spliterator#SUBSIZED}, and {@link Spliterator#NONNULL}.
@@ -810,23 +819,20 @@ public class PriorityQueue<E> extends Ab
      * @since 1.8
      */
     public final Spliterator<E> spliterator() {
-        return new PriorityQueueSpliterator<>(this, 0, -1, 0);
+        return new PriorityQueueSpliterator(0, -1, 0);
     }
 
-    static final class PriorityQueueSpliterator<E> implements Spliterator<E> {
+    final class PriorityQueueSpliterator implements Spliterator<E> {
         /*
          * This is very similar to ArrayList Spliterator, except for
          * extra null checks.
          */
-        private final PriorityQueue<E> pq;
         private int index;            // current index, modified on advance/split
         private int fence;            // -1 until first use
         private int expectedModCount; // initialized when fence set
 
         /** Creates new spliterator covering the given range. */
-        PriorityQueueSpliterator(PriorityQueue<E> pq, int origin, int fence,
-                                 int expectedModCount) {
-            this.pq = pq;
+        PriorityQueueSpliterator(int origin, int fence, int expectedModCount) {
             this.index = origin;
             this.fence = fence;
             this.expectedModCount = expectedModCount;
@@ -835,29 +841,28 @@ public class PriorityQueue<E> extends Ab
         private int getFence() { // initialize fence to size on first use
             int hi;
             if ((hi = fence) < 0) {
-                expectedModCount = pq.modCount;
-                hi = fence = pq.size;
+                expectedModCount = modCount;
+                hi = fence = size;
             }
             return hi;
         }
 
-        public PriorityQueueSpliterator<E> trySplit() {
+        public PriorityQueueSpliterator trySplit() {
             int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
             return (lo >= mid) ? null :
-                new PriorityQueueSpliterator<>(pq, lo, index = mid,
-                                               expectedModCount);
+                new PriorityQueueSpliterator(lo, index = mid, expectedModCount);
         }
 
         @SuppressWarnings("unchecked")
         public void forEachRemaining(Consumer<? super E> action) {
             int i, hi, mc; // hoist accesses and checks from loop
-            PriorityQueue<E> q; Object[] a;
+            final Object[] a;
             if (action == null)
                 throw new NullPointerException();
-            if ((q = pq) != null && (a = q.queue) != null) {
+            if ((a = queue) != null) {
                 if ((hi = fence) < 0) {
-                    mc = q.modCount;
-                    hi = q.size;
+                    mc = modCount;
+                    hi = size;
                 }
                 else
                     mc = expectedModCount;
@@ -868,7 +873,7 @@ public class PriorityQueue<E> extends Ab
                                 break;
                             action.accept(e);
                         }
-                        else if (q.modCount != mc)
+                        else if (modCount != mc)
                             break;
                         else
                             return;
@@ -884,11 +889,11 @@ public class PriorityQueue<E> extends Ab
             int hi = getFence(), lo = index;
             if (lo >= 0 && lo < hi) {
                 index = lo + 1;
-                @SuppressWarnings("unchecked") E e = (E)pq.queue[lo];
+                @SuppressWarnings("unchecked") E e = (E)queue[lo];
                 if (e == null)
                     throw new ConcurrentModificationException();
                 action.accept(e);
-                if (pq.modCount != expectedModCount)
+                if (modCount != expectedModCount)
                     throw new ConcurrentModificationException();
                 return true;
             }
@@ -896,7 +901,7 @@ public class PriorityQueue<E> extends Ab
         }
 
         public long estimateSize() {
-            return (long) (getFence() - index);
+            return getFence() - index;
         }
 
         public int characteristics() {