从名字上看，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;
网友评论