优先队列算法-数据结构java

优先队列有什么用？可以求一些数据里的最大几个值，可以设定事件顺序。
为什么不直接排序后再从头拿？
假设数据量很大时，比如1亿个选10个最大的，你排好序内存可能装不下。优先队列只要10个空间，直接往队列尾巴插入就行。
基础优先队列的基础是把数据构造完全二叉树结构，用数组实现。

文章图片

树的特性

父节点比任何一个子节点大。
父节点的位置是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/2 private 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