上一篇我们知道了PriorityDeque的底层结构,是个平衡二叉堆,用“兵阵变队列”的方式储存在数组中。
这一篇我们开始学习,PriorityDeque是如何利用平衡二叉堆实现优先级排序的。
先看添加元素的方法:
public boolean add(E e) {
return offer(e);
}
原来add
是offer
封装而已,看看offer
源码:
public boolean offer(E e) {
if (e == null)
throw new NullPointerException();
modCount++;
int i = size;
if (i >= queue.length)
grow(i + 1);
siftUp(i, e);
size = i + 1;
return true;
}
offer
添加元素的逻辑如下:
- modCount操作次数加1,默认是0
- size是队列长度,默认是0
- 如果数组长度不够,则需要调用
grow
扩容 - 数组长度足够,调用
siftUp
进行元素添加 - 队列长度size加1
grow
函数我们比较熟悉了,基本上java里面的自动数组扩容都是这个逻辑:长度在64以下是扩容至原长度2倍+2;大于64长度就是每次扩容50%。当然会充分考虑一些越界问题。
private void grow(int minCapacity) {
int oldCapacity = queue.length;
// Double size if small; else grow by 50%
int newCapacity = ArraysSupport.newLength(oldCapacity,
minCapacity - oldCapacity, /* minimum growth */
oldCapacity < 64 oldCapacity + 2 : oldCapacity >> 1
/* preferred growth */);
queue = Arrays.copyOf(queue, newCapacity);
}
接下来,我们重点看之前没见过的函数siftUp(int k, E x)
:
/**
* Inserts item x at position k, maintaining heap invariant by
* promoting x up the tree until it is greater than or equal to
* its parent, or is the root.
*
* To simplify and speed up coercions and comparisons, the
* Comparable and Comparator versions are separated into different
* methods that are otherwise identical. (Similarly for siftDown.)
*
* @param k the position to fill
* @param x the item to insert
*/
private void siftUp(int k, E x) {
if (comparator != null)
siftUpUsingComparator(k, x, queue, comparator);
else
siftUpComparable(k, x, queue);
}
siftUp
的逻辑如下:
- 如果我们构造函数时候传入了自定义的
comparator
比较器,就用siftUpUsingComparator
进行优先级判断加入; - 如果没有自定义比较器,就用默认的
siftUpComparable
函数进行排序后再加入。
注释提到,siftUp
实现在数组的k位置插入元素x,通过“上浮”x直到它大于或等于其父节点,或者x变成根节点,来保持最小堆的平衡,就是“小顶堆”。为了简化和加速比较,默认比较器和自定义比较器被分成不同的方法,其他实现是相同的。(类似siftDown。)
那么,既然注释siftUpComparable
和siftUpUsingComparator
就差个自定义比较而已,那么我们先看默认的排序函数siftUpComparable
的实现逻辑:
/**
* 将元素x插到数组k的位置.
* 然后按照元素的自然顺序进行堆调整——"上浮",以维持"堆"有序.
* 最终的结果是一个"小顶堆".
*/
private static <T> void siftUpComparable(int k, T x, Object[] es) {
Comparable<super T> key = (Comparable<super T>) x;
// 这个k就是我们传进来的队列长度,默认是0
while (k > 0) {
// (k-1)除2, 求出k结点的父结点索引parent
// 例如,k等于1或者2,那么k的父节点在数组位置0
// 如果,k等于3,那么k的父节点在数组位置1
int parent = (k - 1) >>> 1;
// 取出父节点的元素
Object e = es[parent];
// 如果插入的元素值大于等于父结点元素值, 则退出“上浮”循环
if (key.compareTo((T) e) >= 0)
break;
// 如果插入的元素值小于父结点元素值, 则把父节点放到k的位置
es[k] = e;
// 继续向上找下一个父节点是否需要上浮调整
k = parent;
}
// 上浮调整结束,找到适合元素key的位置k,保存到数组中
es[k] = key;
}
原来,siftUpComparable
方法的作用其实就是堆的“上浮调整”,可以把平衡二叉堆想象成一棵完全二叉树,每次插入元素都链接到二叉树的最右下方,然后将插入的元素与其父结点比较,如果父结点大,则交换元素,直到没有父结点比插入的结点大为止。这样就保证了堆顶(二叉树的根结点)一定是最小的元素。(注:以上仅针对“小顶堆”)
再看看siftUpUsingComparator
,只是if那句换成if (key.compareTo((T) e) >= 0)
而已,所以就不再重复阐述了。
如果换成自定义的优先级比较器。可以想象银行的各种金卡黑卡普通卡排队比较。只要金卡来了,就会排比黑卡、普通卡排前面。黑卡来了也可以插普通卡的队。
“有钱大晒啊?”
“抱歉,有钱是真的能为所欲为的。”
这种操作就是折半法查找,每找一次排除一半的可能,256个数据中查找只要找8次就可以找到目标,2^x =N,所以时间复杂度x=Ο(logN)。
ok,总结下今天的结论:
- PriorityQueue的默认优先级是数值从小到大排序
- 排序比较的过程就是堆的上浮处理过程,可以想象银行金卡、黑卡各种插队普通卡
- 上浮算法的关键是通过 (k - 1) / 2 找到k的父节点,再根据优先级是否调换位置
- 时间复杂度是Ο(logN)