PriorityQueue优先级队列源码分析

从名字上看，PriorityQueue叫做优先队列，它的另一个名字也叫堆(heap)，这个名字更熟悉。它和普通的队列不太一样，它里面存储的元素具有一定的顺序性，而不是简单的先进先出。它的实现原理通常是一颗完全二叉树。

优先队列的整体结构虽然是一个二叉堆，也是树结构。但是存储元素却是用数组实现的。

这就是一颗完全二叉树，转换为数组的话就是[50,22,70,10,5]

假设优先队列的第一个元素的索引就是数组中索引为0的元素，其中优先队列的一个节点对应数组的索引是parent，那么左儿子节点索引就是left，右儿子节点索引是right，则存在下面的关系：

left=2*parent+1；right=left+1

parnet=left/2 ；parent=(right-1)/2

先看构造方法：

构造函数

默认容量大小为11

保存元素的数组，同样是一个二叉堆

集合队列元素数量size

比较器，自定义比较逻辑，决定是大根堆还是小根堆

集合修改次数

根据几个成员变量，可以知晓PriorityQueue内部使用数组实现二叉堆，默认的容量为11。

这里这个queue的成员变量的数组长度就是initialCapactity容量大小。

下面我们来分析下offer方法：

当队列元素大小大于等于这个内部数组大小时就扩容，下面我们来看扩容grow方法。

扩容的本质也是利用Arrays.copyOf方法进行元素复制，重点在于数组的大小

oldCapacity<64   -> newCapacity=oldCapacity*2+2

oldCapacity>64   -> newCapac=1.5*oldCapacity

https://www.bilibili.com/video/BV1tW411j7dL/?spm_id_from=333.999.0.0&vd_source=651b32e608fe895ed2b8d03e9549740b(4:45秒开始这个视频讲的非常好动画)

下面来说下当执行aaa.offer(26)过程：

当执行到siftUpComparable方法时，这里的参数k为8(以前队列元素就是8个)，x为添加的元素26。

1 将x(26)强制转换成key，为了方便比较。

2 开启while循环，获取parent节点为:（8-1)>>>1 =3,设置e为40

3 比较26与40大小，key<e，那么就将queue[8]=40,

4 下一步将parent赋值给k,这时k=3。再执行获取e元素，这时e元素为queue[(3-1)/2]=1,比较queue[1]=30,与26大小，key还是小于e，那么就将queue[3]=30,

这时候k=1,parent=0，比较26与10大小，不满足，结束循环。

最后queue[1]=26。    ( 始终是拿26与父节点去比较。 )

这里也可以证明是上述是对的queue[1]为26，queue[3]=30,queue[8]=40。

下面我们来看poll方法：

调用poll方法，会删除最小元素，即堆顶元素。

删除之后，若把末尾元素直接放到堆顶，则破坏了堆的平衡。

先举个例子：

在执行aaa.poll方法之前元素二叉树这么排列的。

接下来就会调用siftDownComparable(int k, E x) 此时这里的k为0，x为40。

排列的

1 强转，方便使用compareTo方法进行比较。

2 获取half值，这里一直循环到是叶子节点。half=8/2=4

3 开始循环，获取child的值为k=0*2+1=1

4 获取queue[1]=26; right=1+1=2;queue[2]=20;

5 如果右节点right<size表面存在右节点，且左右节点比较。如果右子节点的元素比左子节点的元素小，那么使用右子节点的值。将right赋值给child，并且将queue[child=right]，如果右节点大的话比左节点，那么c就是原来左节点的值。

6 如果key=x=40和c左右节点的最小值比较，40>queue[2]，那么queue[0]=c=20;

7 将child=2赋值给k,此时k=2。

第二次循环：

获取child=2*2+1=5 right=6 ;queue[left]=50;queue[right]=25; 所以再拿25和key=40比较，那么queue[K=2]=25，再执行k=child，此时k=6;再来执行while(k<half)进不去循环体内容，直接跳出，执行queue[k]=key 。那么queue[6]=40。

所以queue[0]=20;queue[2]=25;queue[6]=40;