2018-04-12发表数据结构和算法

数据结构（五）优先队列和堆排序

有时候我们会收集一些元素，然后处理当前键值最大的元素。然后再收集更多，再处理。例如，在手机来电、短信、游戏三个程序中，来电的优先级是最高的，我们总希望先处理来电请求。

满足这种场景的数据结构，需要支持两种操作：删除最大（或最小）元素、插入元素。这种数据类型，就叫优先队列。优先队列也是一种队列，但是跟前面提到的先进先出队列不同，优先队列的“出”，是根据优先级来的（最大或最小的先出）。

priorityqueue

优先队列在很多地方有应用，例如：

数据压缩：哈夫曼编码算法
最短路径算法：Dijkstra算法
最小生成树算法：Prim算法
事件驱动仿真：顾客排队算法
选择问题：查找第k个最小元素

初级实现

数组（无序）

我们可以用前面提到的下压栈的方式来实现优先队列。只是在其中加入一段内循环代码，将最大元素和栈顶元素交换，然后弹栈删除它。

数组（有序）

在插入操作中添加代码，将较大的元素往右边移动一格，以保证数组有序。这样，栈顶的元素永远是最大的，弹栈删除即可。

链表实现

可以用前面提到的基于链表的下压栈。修改 pop() 找到并返回最大的元素，或者修改 push() 保证所有元素逆序，并用 pop() 删除并返回链表的首元素（最大元素）。

不同实现的比较

实现	插入	删除	寻找最小值
无序数组	1	n	n
无序链表	1	n	n
有序数组	n	1	1
有序链表	n	1	1
二叉搜索树	logn(平均)	logn(平均)	logn(平均)
平衡二叉搜索树	logn	logn	logn
二叉堆	logn	logn	1

完全二叉树

在讨论堆之前，得先了解一下什么是 完全二叉树（Complete Binary Tree）。在一颗二叉树中，每一个结点都与深度为K的满二叉树中编号从 1 至 n 的结点一一对应，这样的二叉树称为完全二叉树。

CBT

堆

什么是堆

所谓堆，就是利用树的结构来维护一组数据。我们平时说的堆，一般都是指 二叉堆 。如果在一颗完全二叉树中，每个结点都 大于等于 它的两个子节点，那么我们就说这个完全二叉树是 堆有序 的。一组能以堆有序的完全二叉树排序、并在数组中按层级存储的元素，我们就称为二叉堆。二叉堆能够比初级实现更好地实现优先队列。

要点:

完全二叉树
堆有序（父节点 >= 两个子节点）

堆的性质

在一个基于完全二叉树的堆中，如果下标从 1 开始，那么 k 的两个子节点分别为 2k 和 2k+1。如果下标从 0 开始，那么 k 的两个子节点分别为 2k+1 和 2(k+1)

通过这个性质，我们可以轻易计算出某个节点的父节点以及子节点的下标。这也就是为什么可以直接用数组来存储堆的原因。

堆有序化

上浮法实现堆有序化

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

下沉法实现堆有序化

sink

private void sink(int k){

    // k 是参考结点， 2*k 是左子结点， <= N 确保子结点有元素
    while (2*k <= N){
        // j 是子结点，我们要把参考结点跟比较大的子结点做比较
        //由于不知道左子结点比较大还是右子结点比较大
        // 默认为 左子结点
        int j = 2*k;

        // 左右子节点比较，如果 左子 < 右子，j改为右子
        if ( j<N && less(j,j+1))  j++;

        // 参考结点跟比较大的子结点比较，如果子结点比较小，直接退出
        if ( !less(k,j)) break;

        // 如果子结点比较大，把比较小的参考结点沉下去
        exch(k,j);

        // 把子结点作为参考结点，继续循环
        k = j;
    }
}

基于堆的优先队列

算法 2.6

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

    public MapPQ(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;
    }
}

堆排序

基于优先队列的排序方法：将所有元素插入一个查找最小元素的优先队列，然后重复调用删除最小元素的操作，将他们按顺序删去。

堆排序就是一种这样的方法。分为两个阶段：

构造堆：将数组以堆的形式安排
下沉排序：按递减顺序取出所有元素，得到排序结果

算法2.7

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);
    }
}

排序算法总结

算法	稳定性	原地	时间复杂度	空间复杂度	备注
选择排序	不稳定	是	N²	1
插入排序	稳定	是	(N,N²)	1	取决于输入元素的排列情况
希尔排序	不稳定	是	NlogN ?	1
快速排序	不稳定	是	NlogN	lgN	效率由概率提供保证
三向快速排序	不稳定	是	(N,NlogN)	lgN
归并排序	稳定	否	NlogN	N
堆排序	不稳定	是	NlogN	1

快速排序是最快的通用排序算法。Java系统库中 java.util.Arrays.sort() 根据不同的类型参数使用了不同的排序方法。对于原始数据类型，Java选择了三向快速排序，而对于引用类型，则是用归并排序。这些选择实际上是用速度和空间来换取稳定性。

本文部分内容参考自：

数据结构与算法(4)——优先队列和堆

#数据结构和算法