Queue 源码分析
Queue 的实现比较多
Priority Queue 源码分析
java.util.PriorityQueue 是优先级队列的实现，底层依赖的核心数据结构是二叉堆，支持插入元素、删除元素、peek、poll、查找等核心功能；现从以下几点进行分析：
1. 使用的数据结构介绍
PriorityQueue 使用了二叉堆，堆是一个完全二叉树，且每个节点大于（或者小于）他的左右子节点。完全二叉树这种数据结构非常适合使用数组来存储，从 PriorityQueue 源码中也得到证实，使用了 transient Object[] queue; 作为存储元素的容器；所有对 PriorityQueue 的操作其实都是对这个二叉堆的操作，下面我们会分析各种操作的具体方法和复杂度。
使用数组存储时，位置在n的节点，他的两个自己点的位置分别为：2*n+1和2*(n+1)
2. 容量增长策略
public PriorityQueue();
public PriorityQueue(int initialCapacity);
public PriorityQueue(int initialCapacity, Comparator<? super E> comparator);
...
PriorityQueue 提供了数个构造方法，可以指定初始容量，如果不指定，默认是11；同时还可以指定 Comparator 接口，这个我们先忽略，这个只是用于比较两个对象的大小。
PriorityQueue 是使用数组存储的，那么容量是一个很关键的问题，分析可知，PriorityQueue 通过 grow 函数进行扩容，策略是：当前容量小于64时，每次翻倍；当前容量大于64时，每次增长50%；扩容的过程是：计算新的容量 -> 申请新的数组 -> copy到新数组。
3. 核心API及分析（插入，删除，修改，查找/检查）
public boolean offer(E e) {
// null 检查，直接抛出运行时异常
if (e == null)
throw new NullPointerException();
modCount++;
int i = size;
// 判断数组容量，否则就扩容
if (i >= queue.length)
grow(i + 1);
// 底层数组容量+1
size = i + 1;
// 如果是第一个元素，放在第一个即可
if (i == 0)
queue[0] = e;
// 不是第一个元素，进行堆化过程，以满足堆的特性
else
siftUp(i, e);
return true;
}
// 堆化的插入过程, 这个过程是一个从下往上找的过程，直到堆顶或者中途结束
private void siftUpComparable(int k, E x) {
Comparable<? super E> key = (Comparable<? super E>) x;
while (k > 0) {
// 找到位置k的父节点的位置, (k - 1) >>> 1 是无符号右移操作，相当于 (k - 1) / 2
int parent = (k - 1) >>> 1;
// 暂存父节点位置的元素
Object e = queue[parent];
// 和父节点位置的元素比较一下，如果要插入的元素小于父节点，就退出
if (key.compareTo((E) e) >= 0)
break;
// 否则，把父节点下移
queue[k] = e;
// 继续往上找
k = parent;
}
// 找到了合适的插入位置，就把要插入的元素放进去
queue[k] = key;
}
时间复杂度分析，核心操作是插入堆化，每次查找就除2，可以简单评估出 2 ^ k = n, 最大查找次数 k = logn, 所以时间复杂度是 O(logn); 由于整个过程中并没有占用额外空间，空间复杂度是 O(1)
// 定位指定元素，找到位置并返回
private int indexOf(Object o) {
if (o != null) {
for (int i = 0; i < size; i++)
if (o.equals(queue[i]))
return i;
}
return -1;
}
// 这个删除的核心方法，删除指定位置的元素，删除后需要堆化，这个过程会有些复杂
private E removeAt(int i) {
// assert i >= 0 && i < size;
modCount++;
int s = --size;
// 如果是删除最后一个元素，直接删掉
if (s == i) // removed last element
queue[i] = null;
else {
// 取最后一个元素暂存，并删除最后一个元素
E moved = (E) queue[s];
queue[s] = null;
// 进行删除的堆化过程，以满足堆的特性，主要是将最后一个元素插入到合适位置
siftDown(i, moved);
// 这里的意思是，如果删除的是叶子节点，就走插入堆化的流程，可参考上面的分析
if (queue[i] == moved) {
siftUp(i, moved);
if (queue[i] != moved)
return moved;
}
}
return null;
}
// 这个是从上到下的堆化过程，其中 k 是要删除的位置，x 是要插入的元素
private void siftDownComparable(int k, E x) {
Comparable<? super E> key = (Comparable<? super E>)x;
// 为什么取一半? 主要是因为n个节点的堆，他的叶子节点的个数是 n/2, 如果是叶子节点的删除，只需要做
// 从下到上的堆化过程即可，走插入流程；非叶子节点先进行从上到下的堆化
int half = size >>> 1; // loop while a non-leaf
while (k < half) {
int child = (k << 1) + 1; // assume left child is least
Object c = queue[child];
int right = child + 1;
// 左右节点比较，如果右节点大就使用右节点
if (right < size &&
((Comparable<? super E>) c).compareTo((E) queue[right]) > 0)
c = queue[child = right];
// 如果要移动的左右节点小于要插入的数据就终止
if (key.compareTo((E) c) <= 0)
break;
// 把较大的子节点移动到父节点的位置
queue[k] = c;
// 继续向下移动
k = child;
}
// 插入到合适的位置
queue[k] = key;
}
梳理下删除的流程就是： 1. 先找到删除元素的位置，不存在，就退出了 2. 取最后一个元素当作初始需要移动的数据，将这个元素插入到合适的位置（为什么是最后一个元素，我想是这样操作起来是最方便的把，不然，要保证是完全二叉树还是挺麻烦的） 3. 如果删除的元素是非叶子节点，就从他的子节点里找合适的节点往上移动，同时还要和取出来的最后一个元素比较，谁大谁就留在那个位置，就这样一直比较下去，直到叶子节点或者中途退出 4. 如果删除的是叶子节点，或者取出的最后一个元素比删除的元素的子节点都大（还需要看是不是比删除元素的父节点也大，所以需要向上做堆化），就需要做一个从下向上的插入堆化过程
这些操作都比较简单： poll: 取堆顶元素，然后做一个从上到下的堆化过程，可以参考 remove 的 siftDownComparable 流程，时间复杂度O(logn) peek: 取数组第一个元素返回即可，时间复杂度O(1) contains: 遍历数组一遍，找是否有相等的元素，时间复杂度O(n)
到此 PriorityQueue 的核心功能基本分析完成。
