优先队列有什么用？

能够求一些数据里的最大几个值，能够设定事件程序。

为什么不间接排序后再从头拿？

假如数据量很大时，比方1亿个选10个最大的，你排好序内存可能装不下。优先队列只有10个空间，间接往队列尾巴插入就行。

根底

优先队列的根底是把数据结构齐全二叉树构造，用数组实现。

树的个性
  1. 父节点比任何一个子节点大。
  2. 父节点的地位是k，子节点别离是2k和2k+1

优先队列应用时，每次都从根节点拿数据，而后从新调整树结构。

插入与删除

插入时，数据插入到尾部，而后用【上浮】操作使其到适合地位，达成有序。

public void insert(Key v){        pq[++N] = v;        swim(N);}

删除时，移除删除节点，同时把尾部的节点换到删除地位，而后用【下沉】操作使其到适合地位，达成有序。

/** * 删除。该数组0地位不存数据，从1开始存。 * @return*/public Key deleteMax(){    Key key = pq[1];    exchange(1, N--);    pq[N+1] = null;    sink(1);    return key;}
上浮

对应插入操作。新插入的数据放在开端，它必然突破了本来树的有序性。这时须要将插入的节点和父节点比拟。

如果该节点比父节点大，则替换他们地位。达成【父节点比子节点大】这个个性。而后再一直与上一级的父节点比拟，直到满足个性。

//由个性2得：当子节点是k时，父节点地位是k/2private void swim(int k){        while (k > 1 && less(k/2, k)){            exchange(k, k/2);            k = k/2;        }}
下沉

对应删除操作。原先删除的地位被最尾部的节点取代，这也突破了树的有序性。这时该节点要和和子节点比拟，首先得有子节点，其次要选大的那个子节点（这样选出来的节点能力胜任父节点），说白了就是该节点，与两个子节点之间选个最大的当父节点。选到适合的子节点作为父节点后，再往一直下一级比拟，直到没有子节点或者有序。

private void sink(int k){        //这个条件是保障有叶子节点        while (2 * k < N){            //左子节点的坐标            int j = 2 * k;            //这一段是比拟左右叶子节点哪个大，要选大的那个            if(j < N && less(j, j+1)){                j++;            }            //如果k > j,阐明排序失常，间接退出，k < j时替换它们的地位，持续向下比拟            if(!less(k, j)){                break;            }            exchange(k, j);            k = j;        }    }
Java里有对应的实现

线程平安：PriorityBlockingQueue

线程不平安：PriorityQueue