优先队列有两种：最大优先队列，以后最大的元素优先出队；最小优先队列，以后最小的元素优先出队。

PriorityQueue 通过用数组示意的小顶堆来实现，具体构造如下图所示

首先任何结点都小于其左右子结点，除此之外，对于任何一个结点，假如它的下标为n：

  • 左子结点：2 * n + 1
  • 右子结点：2 * n + 2
  • 父结点：(n + 1) / 2

1 结构

  1. 成员变量

  2. 构造函数

    看起来有7种实际上只有4种

    除了第一种，其它的是对PriorityQueue 、SortedSet 和其它Collection 进行初始化，其中SortedSet 自身就曾经是排好序，所以不须要通过什么非凡解决，而其它的则须要调用heapify()进行解决。

    进入heapify() 源码能够看到用到了siftDown() 函数，前面会讲到

2 减少

add 和offer 的语义是雷同的，add也是调用了offer ，次要的是扩容函数grow 和筛选函数siftUp 。扩容函数前面讲，先来剖析筛选函数(siftUp/siftDown)。

假如待插入的元素是4，这个gif图有个缺点就是，比拟完后，并不是4和待比拟的结点替换，而是单纯把父节点移下来。

3 删除

siftDown 和siftUp 差不多，都是蕴含有比拟器和没有比拟器两种办法，这里就拿一个剖析即可。

4 查问

因为查问并没有波及构造的变动和调整，所以源码是非常简单的。

5 扩容

扩容产生在增加元素的时候，当size >= queue.length 的时候就会产生扩容。