PriorityQueue相关
默认情况下PriorityQueue使用自然排序法，最小元素先出列。
PriorityQueue是一种无界的，线程不安全的队列。
是一种通过数组实现的，并拥有优先级的队列。
存储的元素要求必须是可比较的对象， 如果不是就必须明确指定比较器。
一般而言，堆为二叉树。
(offer)上移，找父节点；(poll)下移，找还左孩子节点和右孩子（若存在）。
offer，poll都会自动调整堆的排列。
！！！！！！！！！！！！！！！！！
但是！！！x与queue[k]的比较，不是k++;而是垂直的，也就是k变为父亲或者孩子。
！！！！！！！！！！！！！！！！！
所以堆不是二叉搜索树，即在poll下移时，需要比较，child和right的大小，调整c。
1. 自定义比较：降序
PriorityQueue<Integer> queue=new PriorityQueue<>(k, new Comparator<Integer>() {
@Override
// 降序o2>o1，o2在前
// 自然序为升序
public int compare(Integer o1, Integer o2) {
return o2.compareTo(o1);
}
}); o2.compareTo(o1)==compare(o2,o1) .返回（o2-o1）；若o2>o1，返回1；否则返回0或-1。若o2>o1，则o2在前。
自然序为升序。
补充一下：关于int compare(o1,o2); return o1-o2; 返回-1,0,1；
在siftOfUp（offer函数的上移）中比较是
int parent = (k - 1) >>> 1;
Object e = queue[parent];
if (key.compareTo((E) e) >= 0)
break; 若插入的key.compare（堆节点值）>=0 意味着（默认自然序中）插入key>堆节点值，则找到key上移的顶的位置k了，因为是小顶堆，找到比key大的的节点不需要继续比较了，乖乖当儿子就好。
而在siftOfDown（poll的下移）中，返回非正值，key<=c; 插入值key小于等于左右孩子中一个c,所以找到插入x下移的位置了，找到比插入值大的节点就行，乖乖当老子。（堆只能保证最上面的最小或最大，其他的并不是顺序的）。
所以在最小堆中，offer就是儿子找爹，在下面；poll就是老子找儿子，在上面。
if (key.compareTo((E) c) <= 0)
break; ************************************************************************************************************************************
2. 增
PriorityQueue,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);
size = i + 1;
//第一个直接添加，否则，添加并调整堆
if (i == 0)
queue[0] = e;
else
siftUp(i, e);
return true;
}
//调整堆：在k的位置添加x，再调整堆（上移）。
//根据是否自定义compare规则，分为两种：自定义，自然序。
private void siftUp(int k, E x) {
if (comparator != null)
// 自定义
siftUpUsingComparator(k, x);
else
// 自然序
siftUpComparable(k, x);
}
// 上移调整堆,k加入位置，x加入元素
/*
1. 找k的父节点e，如果（按照自定义比较）父节点 e > x，则（x小，不用上移了）break，并设置堆的k位置为新加入元素x；
2. 若x大，则上移：将k位置设为父节点的值，k=parent，继续循环（k>>>1，找父节点），直到找到x的新父节点大于x，x的子节点小于x的位置。
tips：>>>无符号右移
*/
private void siftUpUsingComparator(int k, E x) {
while (k > 0) {
int parent = (k - 1) >>> 1;
Object e = queue[parent];
if (comparator.compare(x, (E) e) >= 0)
break;
queue[k] = e;
k = parent;
}
queue[k] = x;
}
//自然序
private void siftUpComparable(int k, E x) {
Comparable<? super E> key = (Comparable<? super E>) x;
while (k > 0) {
int parent = (k - 1) >>> 1;
Object e = queue[parent];
if (key.compareTo((E) e) >= 0)
break;
queue[k] = e;
k = parent;
}
queue[k] = key;
}
//增加容量
private void grow(int minCapacity) {
int oldCapacity = queue.length;
// Double size if small; else grow by 50%
int newCapacity = oldCapacity + ((oldCapacity < 64) ?
(oldCapacity + 2) :
(oldCapacity >> 1));
// overflow-conscious code
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
queue = Arrays.copyOf(queue, newCapacity);
} 3. 删
poll，自动调整堆
poll源码：
先取最后的元素提到根结点，然后删除最大值，然后再把新的根节点放到合适的位置
/*
--size,返回堆顶元素(queue[0])。
将最后一个元素(queue[s])置于堆顶，再下移，调整位置。(siftDown(0,x))
*/
public E poll() {
if (size == 0)
return null;
int s = --size;
modCount++;
E result = (E) queue[0];
E x = (E) queue[s];
queue[s] = null;
if (s != 0)
siftDown(0, x);
return result;
}
private void siftDown(int k, E x) {
if (comparator != null)
siftDownUsingComparator(k, x);
else
siftDownComparable(k, x);
}
//将x从k处，下移。（k=0,x=原堆最后一个元素）
/*
循环终止条件：k<size的一半
循环内部：找到x的位置
child=k的左孩子，c-左孩子的值，right-右孩子
（左右孩子取大值） if（右孩子不是最后一层 且 右孩子比左孩子值大）：c和child变为右孩子的位置。
（判断是否k为x的位置，此节点的值比x小）if（k的孩子节点比x的值小）break；找到k-x插入的位置了。
（孩子节点上移）
（k下移） k=孩子节点的位置
循环结束：k的位置为x插入的地方。
*/
private void siftDownUsingComparator(int k, E x) {
int half = size >>> 1;
while (k < half) {
int child = (k << 1) + 1;
Object c = queue[child];
int right = child + 1;
if (right < size && comparator.compare((E) c, (E) queue[right]) > 0)
c = queue[child = right];
if (comparator.compare(x, (E) c) <= 0)
break;
queue[k] = c;
k = child;
}
queue[k] = x;
}
//默认
private void siftDownComparable(int k, E x) {
Comparable<? super E> key = (Comparable<? super E>)x;
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;
} 对于优先队列的解释：https://www.cnblogs.com/CarpenterLee/p/5488070.html
