优先行列是在实际工程中被遍及应用的一种数据布局，软件开发，不管是在操纵系统的历程调治中，照旧在相关的图算法好比Prim算法和Dijkstra算法中，我们都可以看到优先行列的身影，本文我们就来阐明一下优先行列的实现道理。

优先行列

以操纵系统的历程调治为例，好比我们在利用手机的进程中，手机分派给来电的优先级城市比其它措施高，在这个业务场景中，我们不要求所有元素全部有序，因为我们需要处理惩罚的只是当前键值最大的元素(优先级最高的历程)。在这种环境下，我们需要实现的只是删除最大的元素(获取优先级最高的历程)和插入新的元素(插入新的历程)，这种数据布局就叫做优先行列。

我们先来界说一个优先行列，下面我们将利用pq[]来生存相关的元素，在结构函数中可以指定堆的初始化巨细，假如不指定初始化巨细值，默认初始化值为1。p.s: 在下面我们会实现相关的resize()要领用来动态调解数组的巨细。

public class MaxPQ<Key> implements Iterable<Key> {
    private Key[] pq;                    // store items at indices 1 to n
    private int n;                       // number of items on priority queue
    private Comparator<Key> comparator;  // optional Comparator
    /**
     * Initializes an empty priority queue with the given initial capacity.
     *
     * @param  initCapacity the initial capacity of this priority queue
     */
    public MaxPQ(int initCapacity) {
        pq = (Key[]) new Object[initCapacity + 1];
        n = 0;
    }
    /**
     * Initializes an empty priority queue.
     */
    public MaxPQ() {
        this(1);
    }
}

堆的根基观念

在正式进入优先行列阐明之前，我们有须要先相识一下对付堆的相关操纵。我们界说当一棵二叉树的每个结点都要大于便是它的两个子结点的时候，称这棵二叉树堆有序。如下图就是一棵典范的堆有序的完全二叉树。

堆上浮和下沉操纵

对了担保堆有序，对付堆我们要对它举办上浮和下沉操纵，我们先来实现两个常用的东西要领，个中less()用于较量两个元素的巨细，exch()用于互换数组的两个元素：

private boolean less(int i, int j) {
    if (comparator == null) {
        return ((Comparable<Key>) pq[i]).compareTo(pq[j]) < 0;
    }
    else {
        return comparator.compare(pq[i], pq[j]) < 0;
    }
}
private void exch(int i, int j) {
    Key swap = pq[i];
    pq[i] = pq[j];
    pq[j] = swap;
}

上浮操纵

按照下图我们首先来阐明一下上浮操纵，软件开发，以swim(5)为例子，我们来看一下上浮的进程。对付堆我们举办上浮的目标是保持堆有序性，即一个结点的值大于它的子结点的值，所以我们将a[5]和它的父结点a[2]对较量，假如它大于父结点的值，我们就互换两者，然后继承swim(2)。

详细的实现代码如下：

private void swim(int k) {
    while (k > 1 && less(k/2, k)) {
        exch(k, k/2);
        k = k/2;
    }
}

下沉操纵

按照下图我们来阐明一下下沉操纵，以sink(2)为例子，我们先将结点a[2]和它两个子结点中较小的结点对较量，软件开发，假如小于子结点，我们就互换两者，然后继承sink(5)。

详细的实现代码如下：

private void sink(int k) {
    while (2*k <= n) {
        int j = 2*k;
        if (j < n && less(j, j+1)) j++;
        if (!less(k, j)) break;
        exch(k, j);
        k = j;
    }
}

实现

我们来阐明一下插入一个元素的进程，假如我们要在堆中新插入一个元素S的话，首先我们默认将这个元素插入到数组中pq[++n] 中(数组是从1开始计数的)。当我们插入S后，冲破了堆的有序性，所以我们回收上浮操纵来维持堆的有序性，当上浮操纵竣事之后，我们依然可以担保根结点的元素是数组中最大的元素。

接下来我们来看一下删除最大元素的进程，我们首先将最大的元素a[1]和a[n]互换，然后我们删除最大元素a[n]，这个时候堆的有序性已经被冲破了，所以我们继承通过下沉操纵来从头维持堆的有序性，保持根结点元素是所有元素中最大的元素。