JDK容器学习之Queue: PriorityQueue

// 存储队列元素的数组
transient Object[] queue;

// 队列中实际元素的个数
private int size = 0;

// 比较器，用于定义队列中元素的优先级
private final Comparator<? super E> comparator;

public E poll() {
  if (size == 0)
      return null;
  int s = --size;
  modCount++;
  // 第一个元素为队列头
  E result = (E) queue[0];
  E x = (E) queue[s];
  queue[s] = null;
  if (s != 0)
  // 队列非空，对剩下的元素进行重排
      siftDown(0, x);
  return result;
}

private void siftDown(int k, E x) {
    if (comparator != null)
        siftDownUsingComparator(k, x);
    else
        siftDownComparable(k, x);
}

private void siftDownUsingComparator(int k, E x) {
    int half = size >>> 1;
    while (k < half) {
        int child = (k << 1) + 1;
        Object c = queue[child];
        int right = child + 1;
        if (right < size &&
            comparator.compare((E) c, (E) queue[right]) > 0)
            c = queue[child = right];
        if (comparator.compare(x, (E) c) <= 0)
            break;
        queue[k] = c;
        k = child;
    }
    queue[k] = x;
}

public boolean offer(E e) {
    if (e == null) // 非null
        throw new NullPointerException();
    modCount++;
    int i = size;
    if (i >= queue.length) // 动态扩容
        grow(i + 1);
    size = i + 1;
    if (i == 0)
        queue[0] = e;
    else
        siftUp(i, e);
    return true;
}


// 扩容逻辑，扩容为新size的两倍，或者新增原来容量的一半
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);
}

// 二叉树重排
private void siftUp(int k, E x) {
    if (comparator != null)
        siftUpUsingComparator(k, x);
    else
        siftUpComparable(k, x);
}

private void siftUpUsingComparator(int k, E x) {
    while (k > 0) {
        int parent = (k - 1) >>> 1;
        Object e = queue[parent];
        if (comparator.compare(x, (E) e) >= 0)
            break;
        queue[k] = e;
        k = parent;
    }
    queue[k] = x;
}