Heap-Sort

1. 优先队列

学习堆排序前，需要先了解优先队列是什么东西，引出数据结构：堆，最后学习堆排序。优先队列和普通的队列一样是一种数据结构，普通队列遵循的原则就是先进先出（FIFO）。而优先队列则是无论入队顺序，当前队列中优先级最高的元素先出。谈到优先级就有两种确定优先级的策略，一是值小的优先级高，二是值大的优先级高。这也就把优先队列分为了两种：

1. 最大优先队列：无论入队顺序，当前队列中最大的元素出队列。

2. 最小优先队列：无论入队顺序，当前队列中最小的元素出队列。

由于二者实现原理类似，下面的优先队列默认是最大优先队列。

2. 初级实现

在还不知道堆之前，我们用一般的数据结构去实现优先队列也是可行的，但是由于数据结构的限制，算法的性能可能是比较低的。

1. 基于无序数组实现

使用无序的数组在插入元素时，可以添加任意添加到数组中一个空位置。在取出最大元素时需要遍历一遍数组找出最大元素，让其与边界元素交换位置然后删除出队。可以添加代码自动的调整数组大小防止元素溢出。

2. 基于有序数组实现

在插入每一个新元素时，将比它大的元素都右移一位然后将其插入数组来保持数组的有序性（插入排序）。这样数组中最大的元素总是在数组的最右边，每次让元素出队列直接选择最右边的元素就完了。当然上述的两种实现用链表也能实现。基于链表实现在插入，移动元素时有一定的优势，但是在遍历数组时没有数组的效率高，在此不再赘述。

在对于普通队列或栈的实现时，我们使用数组实现，能够使其所有操作都在常数时间内完成。而上述两种初级实现方法，插入元素或删除最大元素的两种操作之一在最坏情况下需要线性的时间来完成，这显然是不怎么好的。而堆这种数据结构能好的实现优先队列，可以将插入元素，删除最大元素消耗的时间降低至对数级，如下表所示（log默认以2为底）。

3. 堆的定义

堆在逻辑结构上是一个完全二叉树，所以有时堆也被称为二叉堆。下面介绍几个概念：

1. 满二叉树： 在每一层上的节点数都达到了最大值，即在第 i 层的节点应为2^(i-1)个节点。

2. 完全二叉树： 一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。也就是说，一颗满二叉树，或缺失掉右下角一部分节点的满二叉树就是一颗完全二叉树。

3. 当一棵二叉树的每个结点都大于等于它的两个子结点时，它被称为堆有序。 不难看出在一课堆有序的二叉树中，最大的元素就是二叉树的根节点。

4. 堆的表示

在一般情况下我们表示一颗二叉树都需要在每一个元素中放置3个指针，一个是指向父节点，另外两个指向其两个子节点，方便我们操作二叉树的元素。但是由于堆是一颗完全二叉树，事情就简化了许多，我们仅使用一个数组就可以表示一个堆: **我们将整个堆按层级顺序放置到一个数组中，根节点在位置1，根节点左子节点在位置2，右子节点在位置3，依次类推 。**这样放置后我们可以容易的得到结论：在一个数组表示堆中，位置 k 的结点的父结点的位置为 k/2，而它的两个子结点的位置则分别为 2k 和 2k+1。 这样我们在不使用指针的情况下，也可以找到一个节点的父节点，以及其两个子节点。而且也大幅提高了查找元素的性能。

5. 堆实现优先队列

1. 堆的有序化

前面我们提到了堆有序的概念就是：**当一棵二叉树的每个结点都大于等于它的两个子结点时，它被称为堆有序。**而我们将一个不满足堆有序定义的堆变为一个堆有序的堆的过程就称为堆有序化。 而堆不满足堆有序的原因可分为两个种。 一是：元素的父节值点小于它，它需要上浮来使堆有序。二是：元素节点值小于其两个子节点或两个子节点其中之一，它需要下沉来使堆有序。

1.1 上浮实现

1
2
3
4
5
6
7

//元素上浮
    private void swim(int k){
        while (k>1 && (pq[k/2] < pq[k])){
            exch(k/2, k);
            k = k/2;
        }
    }

1.2 下沉实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

  //元素下沉
    private void sink(int k){
        while (2*k <= N){
            int j = 2*k;
            if (j < N && pq[j]<pq[j+1]) j++;
            //此时 j 为位置为 k 节点的子节点中值较大节点的索引
            if (pq[k] > pq[j]) break;
            exch(k, j);
            k = j;
        }
    }

有了上述两个操作，我们就可以保证在元素变化使，仍然可以让堆重新堆有序化。

2. 堆实现优先列队

根据堆的定义以及其性质，我们就可以很轻松高效的实现优先队列。在插入元素时，将新元素放置在末尾，然后使用swim()函数去操作它使得新堆达到堆有序。在删除元素时，直接删除值最大根节点，然后将末尾节点放置到根节点的位置，最后使用sink()函数使其下沉到合适位置使新堆达到堆有序。具体实现如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

/**
 * 基于堆实现的优先队列
 */
public class MaxPQ {
    private int[] pq;
    private int N = 0;

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

    //返回优先队列长度
    public int size(){
        return N;
    }

    //交换元素位置
    private  void exch(int i, int j){
        int tmp = pq[i];
        pq[i] = pq[j];
        pq[j] = tmp;
    }

    //元素上浮, 参考上文
    private void swim(int k);

    //元素下沉，参考上文
    private void sink(int k);

    //插入元素
    public void insert(int v){
        pq[++N] = v;
        swim(N);
    }

    //删除最大元素
    public int delMax(){
        int max = pq[1];
        //有序化堆
        exch(1, N--);
        pq[N+1] = 0;
        sink(1);
        return max;
    }
}

6. 堆排序

我们可以把任意优先队列变成一种排序方法。将所有元素插入一个查找最大元素的优先队列， 然后再重复调用删除最大元素的操作来将它们按顺序删去。用无序数组实现的优先队列这么做相当于进行一次选择排序。用基于堆的优先队列这样做等同于哪种排序？一种全新的排序方法！下面我们就用堆来实现一种经典而优雅的排序算法——堆排序。

堆排序在操作上分为两个步骤：

1. 用待排序数组元素构造一个堆有序的堆。

2. 取出最大元素，将最后一个元素放置到根节点位置，然后调用sink()函数将新堆有序化。重复此步骤直到数组元素取尽。

明白了这两个步骤后大致也就理解了堆排序的原理。其中步骤1构建一个堆有序的堆的方法有几个，可能最容易想到的就是从左至右扫描数组，使用 swim() 来保证堆有序。但是有一个更聪明高效的方法是使用 sink() 函数，由于完全二叉树的叶子节点数总是大于等于非叶子节点数这个完全二叉树的性质，使用sink()函数只需要处理一遍非叶子节点，所以我们就只需要扫描数组的一半元素。唯一的不足就是sink()的每次循环会有两次比较，比swim()多一次。完整实现的堆排序如下。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

public class HeapSort {

    public static void sort(int[] 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);
        }
    }

    //元素下沉
    private static void sink(int[] a, int k, int N){
        while (2*k <= N){
            int j = 2*k;
            //比较时索引减一，将索引位置由1 ~ n 映射到 0 ~ n-1
            if (j < N && a[j-1] < a[j]) j++;
            //此时 j 为位置为 k 节点的子节点中值较大节点的索引
            if (a[k-1] > a[j-1]) break;
            exch(a ,k, j);
            k = j;
        }
    }

    //交换元素位置
    private static void exch(int[] a, int i, int j){
        //换位置索引减一，将索引位置由1 ~ n 映射到 0 ~ n-1
        i -= 1; j -= 1;
        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }
}

7. 堆排序的优缺点

优点：

1. 堆排序的效率与快排、归并相同，都达到了基于比较的排序算法效率的峰值（时间复杂度为O(nlogn)）

2. 只需要O(1)的辅助空间了，既最高效率又最节省空间。

3. 堆排序效率相对稳定，不像快排在最坏情况下时间复杂度会变成O(n^2)），所以无论待排序序列是否有序，堆排序的效率都是O(nlogn)不变（注意这里的稳定特指平均时间复杂度=最坏时间复杂度，不是那个“稳定”，因为堆排序本身是不稳定的）

缺点：

现代系统的许多应用很少使用它，因为它无法利用缓存。数组元素很少和相邻的其他元素进行比较，因此缓存未命中的次数要远远高于大多数比较都在相邻元素间进行的算法，如快速排序、归并排序，甚至是希尔排序。

但是虽然有这一致命缺点，但是由于其优点太过于吸引人，在一些特殊的场景仍是一种非常重要，优秀的算法。

图片资料来自：

1. Algorithms (4th Edition)

2. GeeksforGeeks