算法笔记六

优先队列和堆排

优先队列

定义：可以移除最大或最小的元素。

API：插入，删除，是否为空，大小

应用：数值计算，数据压缩，图搜索，人工智能，统计学，操作系统，离散优化，垃圾过滤

初级实现：数组实现(无序)，数组实现(有序)，链表实现。

二叉堆

数组实现，实际上并没有显式的连接。

堆有序：当一棵二叉树的每个节点都大于等于它的两个子节点时，它被称为堆有序。
根节点是堆有序的二叉树中的最大节点。
二叉堆是一组能够用堆有序的完全二叉树排序的元素，并在数组中按照层级存储(不使用数组的第一个位置)
主要API在于：swim(),sink();

具体的swim和sink实现：

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

public void insert(Key x){
    pq[++n] = x;
    swim(n);
}

private void sink(int k){
    while(2 * k <= N){
        int j = 2 * k;
        if(j < N && less(j,j+1)){ //这个less()API和之前相似，比较a[j]和a[j+1]的大小
            j++;
        }
        if(!less(k,j)){
            break;
        }
        each(k,j);
        k = j;
    }
}

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

Java 实现

堆排序

利用优先队列可以进行排序方法。堆排序分为两个阶段

• 在堆的构造阶段，我们将原始数组重新组织安排进一个堆中。

• 下沉阶段，我们从堆中按递减顺序取出所有元素并得到排序结果。

public static void sort(Comparable[] a){
    int N = a.length;
    for(int k = N/2;k >=1;k--){
        sink(a,k,N);
    }
    while(N > 1){
        exch(a,1,N--);
        sink(a,1,N);
    }
}