优先队列与堆（一）

定义: 当一棵二叉树的每个结点都大于等于它的两个子结点时，它被称为堆有序。

定义：二叉堆是一组能够用堆有序的完全二叉树排列的元素，并在数组中按照层级存储（不使用数组的第一个位置）。

我们用长度为N+1的数组pq[]来表示一个大小为N的堆，不使用pq[0]而将数组元素放在pq[0]至pq[N]中。堆的操作首先会进行一些简单的改动，打破堆的状态，然后再遍历堆将堆的状态恢复。我们称这个过程为堆的有序化。
在有序化的过程中，我们会遇到两种情况。某个结点的优先级上升（或是在堆的底部加入一个新的元素）时，我们要由下至上恢复堆的顺序；当某个结点的优先级下降（例如，将根结点替换为某个较小的元素），我们需要由上至下恢复堆的顺序。

由下至上的堆有序化（上浮）：
private void swim(int k){
while(k > 1 && less(k/2, k)){
exch(k/2, k);
k = k/2;
}
}
由上至下的堆有序化（下沉）
private void sink(int k){
while(2k <= N){
int j =2k;
if( j<N && less(j, j+1) j++;
if( !less(k,j)) break;
exch(k, j);
k = j;
}
}

基于这两种基本的操作，可以很容易实现插入元素和删除最大元素的操作。

插入元素
我们可以将新元素放置在数组末尾，增加堆的大小并让这个新元素上浮到合适的位置。
删除最大的元素
我们可以从数组的顶端删去最大的元素，并将数组的最后一个元素放到顶端，并让它下沉到合适的位置。

据此我们可以实现基于堆的优先队列：

public class MaxPQ<Key extends Comparable<Key>>{
    private Key[] pq;
    private int N = 0;

    public MaxPQ(int maxN){
        pq = (Key[]) new Comparable[maxN+1];
    }

    public boolean isEmpty(){
        return N == 0;
    }

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

    public Key delMax(){
        Key max = pq[1];
        exch(1,N--);
        pq[N+1] = null;
        sink(1);
        return max;
    }

    private boolean less(int i, int j){
        return pq[i].compareTo(pq[i]) < 0;
    }
    
    private void exch(int i, int j){
        Key t = pq[i];
        pq[i] = pq[j];
        pq[j] = t;
    }
}

针对基于堆的优先队列，我们有如下命题：

对于一个含有N个元素的基于堆的优先队列，插入元素的操作只需要不超过(lgN+1)次的比较，删除最大元素的操作需要不超过2lgN次比较。

优先队列与堆（一）

推荐阅读更多精彩内容