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