基于优先堆实现的无限的优先队列。队列里的元素根据它们自然的顺序或者构造函数传入的Comparator排序。PriorityQueue不允许null元素，依赖于自然顺序的优先队列也不允许无法比较的对象。

• 基于最小堆：队列的头是符合指定顺序的最小的元素，如果多个元素都是最小值，头是他们其中一个。
• 优先队列是无限的，但是有一个内部容量来控制队列上用来存储元素的数组的大小。它总是至少比size大，加入元素时自动增长。
• 非线程安全：多线程操作，使用java.util.concurrent.PriorityBlockingQueue代替。

  Important variables

  1 2 3 4 5

  private static final int DEFAULT_INITIAL_CAPACITY = 11; transient Object[] queue; private int size = 0; // null表示使用自然顺序 private final Comparator<? super E> comparator;

  
  
  PriorityQueue 使用数组来存储二叉堆，如图所示数组存储二叉树有如下性质：
• L=2*P+1
• R=2*P+2
• P=(L-1)/2=(R-2)/2=int((R-2)/2)=(Node-1)/2
  得到以下性质之后，后面代码中都用到。

Main Methods

• grow()

  1 2 3 4 5 6 7 8 9 10

  private void grow(int minCapacity) { int oldCapacity = queue.length; // 如果<64,翻倍；否则增加50%； int newCapacity = oldCapacity + ((oldCapacity < 64) ? (oldCapacity + 2) :(oldCapacity >> 1)); // 检查是否超过最大SIZE：Integer.MAX_VALUE - 8 if (newCapacity - MAX_ARRAY_SIZE > 0) // 允许再扩大到 Integer.MAX_VALUE newCapacity = hugeCapacity(minCapacity); queue = Arrays.copyOf(queue, newCapacity); }

• siftUpUsingComparator()
  在队列末尾加入元素，不断地同父节点进行比较，如果违反父节点小于任意子节点的规则就和父节点交换，直到满足就停止。

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

  private void siftUpUsingComparator(int k, E x) { while (k > 0) { // 和父节点比较 int parent = (k - 1) >>> 1; Object e = queue[parent]; // x大于等于父节点，停止 if (comparator.compare(x, (E) e) >= 0) break; // 将父节点放下来 queue[k] = e; // 从父节点的位置继续网上搜索 k = parent; } queue[k] = x; }

  

• shifrDownUsingComparator()
  从某个位置移除原有元素后，为了收缩空间，将队列尾部的元素放到移除的位置。然后一直同子节点比较，如果违背父节点小于任意子节点的规则，就和子节点进行交换，直到满足就停止。

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

  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; }

  

• add()/offer()
  两者基本相同，前者调用后者实现。加入元素之前确认空间，然后调用shiftUp 也就是 siftUpUsingComparator 实现元素插入并保持优先队列的特性。

  1 2 3 4 5 6 7 8 9 10 11 12

  public boolean offer(E e) { 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; }

• peak()

  1 2 3

  public E peek() { return (size == 0) ? null : (E) queue[0]; }

  获取但不删除，由于再加入或者删除元素时就进行调整以维护优先队列特性，因此堆顶元素就是优先级最高的。

• remove()/pool()
  获取并删除，remove(Object) 表示删除队列中与equal(o) 的对象， removeEq(Object o) 表示删除队列中与==o(同一个对象，更严格)的对象，不过两者在定位到对象后最终都通过 removeAt(i)来移除并保持队列特性；

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

  private E removeAt(int i) { int s = --size; if (s == i) // 移除最后一个元素 queue[i] = null; else { // 取出最后一个元素 E moved = (E) queue[s]; queue[s] = null; // 尝试往下移动 siftDown(i, moved); // 如果没有往下移动成功，则尝试网上移动(理论上不会走到这里) if (queue[i] == moved) { siftUp(i, moved); if (queue[i] != moved) return moved; } } return null; }

  pool() 是移除堆顶元素，移除之后的恢复相对简单：

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

  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; }

Summary

• PriorityQueue的peek()和element操作是常数时间，add(), offer(), 无参数的remove()以及poll()方法的时间复杂度都是*log(N)*。
• 后两张图片来自网上，侵权请联系删除。