Java PriorityQueue源码学习

public class PriorityQueue<E> extends AbstractQueue<E> implements java.io.Serializable 1.5

1. 自动扩容 ，初始化默认11，小于64时2倍扩容，大于64时1.5倍扩容。

   private void grow(int minCapacity) {
       int oldCapacity = queue.length;
       // Double size if small; else grow by 50%
       int newCapacity = oldCapacity + ((oldCapacity < 64) ?
                                        (oldCapacity + 2) :
                                        (oldCapacity >> 1));
       // overflow-conscious code
       if (newCapacity - MAX_ARRAY_SIZE > 0)
           newCapacity = hugeCapacity(minCapacity);
       queue = Arrays.copyOf(queue, newCapacity);
   }
   

2. Add 节点上浮，Remove节点下沉。

   private void siftUpComparable(int k, E x) {
       Comparable<? super E> key = (Comparable<? super E>) x;
       while (k > 0) {
           int parent = (k - 1) >>> 1;
           Object e = queue[parent];
           if (key.compareTo((E) e) >= 0)
               break;
           queue[k] = e;
           k = parent;
       }
       queue[k] = key;
   }
   

   private void siftDownComparable(int k, E x) {
       Comparable<? super E> key = (Comparable<? super E>)x;
       int half = size >>> 1;        // loop while a non-leaf
       while (k < half) {
           int child = (k << 1) + 1; // assume left child is least
           Object c = queue[child];
           int right = child + 1;
           if (right < size &&
               ((Comparable<? super E>) c).compareTo((E) queue[right]) > 0)
               c = queue[child = right];
           if (key.compareTo((E) c) <= 0)
               break;
           queue[k] = c;
           k = child;
       }
       queue[k] = key;
   }
   

3. 构建堆

   private void heapify() {
       for (int i = (size >>> 1) - 1; i >= 0; i--)//非叶子节点开始
           siftDown(i, (E) queue[i]); //下沉
   }
   

4. 总结
   PriorityQueue默认是最小堆，头结点最小。
   O(log(n)) time for the enqueuing and dequeuing methods offer, poll, remove() and add;
   O(n) time for the remove(Object) and contains(Object) methods,先找位置;
   O(1) time for the retrieval methods peek,element, and size.

@梦工厂 2018.3.11