【java容器的刻意练习】【十七】PriorityQueue的插入源码分析【java容器的刻意练习】【十七

上一篇我们知道了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 void siftUpComparable(int k, T x, Object[] es) { Comparable key = (Comparable) 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)而已，所以就不再重复阐述了。