【重温基础算法】内部排序之堆排序法

内部排序之堆排序法

堆排序就是利用堆(Heap)这种数据结构进行排序，在堆排序算法中，我们使用的是最大堆(大根堆)，堆排序是一种选择排序。

二叉堆定义

堆也是指二叉堆，是完全二叉树或者近似完全二叉树。

最大堆：当父结点的键值总是大于或等于任何一个子节点的键值。

最小堆：当父结点的键值总是小于或等于任何一个子节点的键值。

二叉堆的特性

1. 父结点的键值总是大于（小于或等于）任何一个子结点的键值。
2. 每个结点的左子树和右子树都是一个二叉堆（最大堆或最小堆）。

结点拥有的子树的个数称为结点的度(Degree)。

二叉树的特性

1. 在二叉树的第 $\mathrm{i}$ 层上最多有$2^{\mathrm{i}-1}$个结点（$\mathrm{i}\ge 1$）。
2. 深度为 $\mathrm{k}$ 的二叉树至多有$2^{\mathrm{k}}-1$个结点（$\mathrm{k}\ge 1$）。
3. 对任何一颗二叉树$T$，如果其叶子结点个数为${\mathrm{n}}_0$,度为2的结点个数为${\mathrm{n}}_2$,则${\mathrm{n}}_0={\mathrm{n}}_2+1$。

完全二叉树的特性

1. 具有$\mathrm{n}$个节点的完全二叉树的深度为$\lfloor \mathrm{lo}{\mathrm{g}}_2^{\mathrm{n}}\rfloor +1$，按层序编号，编号为i的结点的层次在$\left|\mathrm{lo}{\mathrm{g}}_2^{\mathrm{i}}\right|+1$
2. 一棵深度为 $\mathrm{k}$ 的完全二叉树至少有$2^{\mathrm{k}-1}$的节点，至多$2^{\mathrm{k}}-1$个结点。

逻辑结构

完全二叉树的逻辑结构

存储结构

使用数组来存储元素值。

数组的heapify

下标$0$代表二叉树的根结点，将树按层从上至下，在同一层按从左往右，依次将结点的值存到数组中。如下图：

若数组下标为$i$，则其左子树的下标为$2\ast i+1$，右子树的下标为$2\ast i+2$。其父结点的下标为$\frac{i-1}{2}(i>0)$。

主体思路：

1. 寻找最后一个非叶子结点的下标。
2. 从第一个非叶子结点的下标开始递减遍历数组。
3. 设遍历下标变量用$i$，在遍历过程中，比较其、其左子树的下标为$2\ast i+1$、右子树的下标为$2\ast i+2$的大小，将最大值放在$i$的位置上。直到$i$到0，数组heapify完成。

寻找最后一个非叶子结点

1. 一个完全二叉树是完全填满的情况下，每一层的结点数是上一层的两倍，根结点的个数是1，最后一层的第一个结点（第一个叶子结点）的索引下标就是结点总数/2。那么最后一个非叶子节点的索引下标就是结点总数/2-1。
2. 由于完全二叉树是依次填充，那么，最多存在一个度为1的结点（此结点只拥有一个左子结点），其他结点要么是度为2的结点，要么是度为0的结点。在完全二叉树不完全填满的情况下，总的结点数=度为2的结点个数+度为0的结点个数+1（可以理解度为1的结点个数）。结合上述二叉树的特性三（对任何一颗二叉树$T$，如果其叶子结点个数为${\mathrm{n}}_0$,度为2的结点个数为${\mathrm{n}}_2$,则${\mathrm{n}}_0={\mathrm{n}}_2+1$。），第一个叶子节点的索引下标也为结点总数/2。那么最后一个非叶子节点的索引下标就是结点总数/2-1。

主要思想

1. 将初始数组进行heapify，满足二叉堆的特性。（按最大堆处理）
2. 目前下标$0$的存储值是数组中最大的值，将下标$0$和下标$8$（数组$length-1$）进行交换，此时下标$8$就是最大值。
3. 在下标$8$不参与的情况下，再进行数组的heapify，使得下标$0$存储着剩余数组元素中的最大值，将下标$0$与下标$7$的值进行交换。此时下标$7$，下标$8$已经是经过排序的了。
4. 重复以上步骤，将未排序的数组元素继续heapify和首尾值交换。直到数组完全排序。

过程演示

JAVA代码

package sort;

public class HeapSort {

    /**
     * 将数组进行heapify
     */
    private static void buildHeap(int[] o, int i, int length) {
        int leftChild = 2 * i + 1;
        int rightChild = leftChild + 1;
        int larger = i;

        if (leftChild < length && o[leftChild] > o[larger]) {
            larger = leftChild;
        }
        if (rightChild < length && o[rightChild] > o[larger]) {
            larger = rightChild;
        }
        if (larger != i) {
            int temp = o[i];
            o[i] = o[larger];
            o[larger] = temp;
            buildHeap(o, larger, length);
        }
    }

    public static void main(String[] args) {
        int[] o = {7, 6, 9, 3, 1, 5, 2, 4, 8};
        int count = 1;
        System.out.print("heapify前: ");
        for (int t : o) {
            System.out.print(t);
            System.out.print(" ");
        }
        System.out.println();

        // 算法部分
        // init heapify
        int i = o.length / 2 - 1;
        for (; i >= 0; i--) {
            buildHeap(o, i, o.length);
        }
        System.out.print("第" + count + "趟heapify后: ");
        for (int t : o) {
            System.out.print(t);
            System.out.print(" ");
        }
        System.out.println();

        // sort
        for (int j = o.length - 1; j > 0; j--) {
            int temp = o[j];
            o[j] = o[0];
            o[0] = temp;
            if (j == 1) {
                break;
            }
            buildHeap(o, 0, j);
            count++;
            System.out.print("第" + count + "趟heapify后: ");
            for (int t : o) {
                System.out.print(t);
                System.out.print(" ");
            }
            System.out.println();

        }

        System.out.print("排序后: ");
        for (int t : o) {
            System.out.print(t);
            System.out.print(" ");
        }
        System.out.println();
    }
}
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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76

结果

heapify前: 7 6 9 3 1 5 2 4 8 
第1趟heapify后: 9 8 7 6 1 5 2 4 3 
第2趟heapify后: 8 6 7 4 1 5 2 3 9 
第3趟heapify后: 7 6 5 4 1 3 2 8 9 
第4趟heapify后: 6 4 5 2 1 3 7 8 9 
第5趟heapify后: 5 4 3 2 1 6 7 8 9 
第6趟heapify后: 4 2 3 1 5 6 7 8 9 
第7趟heapify后: 3 2 1 4 5 6 7 8 9 
第8趟heapify后: 2 1 3 4 5 6 7 8 9 
排序后: 1 2 3 4 5 6 7 8 9 
1
2
3
4
5
6
7
8
9
10

算法分析

整个堆排序的算法包含了初始化堆和重建堆两部分。

初始化堆的时间复杂度

在数组的初始堆化中，是从倒数第二层中的最后一个非叶子结点开始的。一个深度为$k$的二叉堆，堆化过程中关键字比较次数一共最多$2(k-1)$。

那么深度为$h$， 元素个数为n的二叉堆，$i$代表堆的第几层，那么$i$的取值就是从$h-1\sim 1$。第i层上至多有$2^{i-1}$个结点，若以$i$为根，那深度为$h-i+1$，得到数组初始堆化的比较耗时公式：$S=\sum _{i=h-1}^1{2}^{i-1}\ast 2\ast (h-i)$。$2\ast (h-i)由2\ast (h-i+1-1)$而来，这代表一个，所以还有乘以这个层的所有结点数。简化后结合$h={\log }_2^n$，可以知$S\le 4n$，时间复杂度为$O(n)$。

$S=\sum _{i=h-1}^1{2}^{i-1}\ast 2\ast (h-i)=\sum _{i=1}^{h-1}{2}^i(h-i)=\sum _{i=1}^{h-1}h\ast 2^j-\sum _{i=1}^{h-1}{2}^{i+1}=4\ast 2^h-2h=4\ast n-2\ast lo{g}_2^n\le 4n⟹O(n)$

重建堆时的时间复杂度

$n$个结点的完全二叉树的深度为$\lfloor \mathrm{lo}{\mathrm{g}}_2\mathrm{n}\rfloor +1$，会使用数组堆化方法n-1次，总的比较次数

$2(\lfloor lo{g}_2(n-1)\rfloor +\lfloor lo{g}_2(n-2)\rfloor +\lfloor lo{g}_2(n-3)\rfloor +...+lo{g}_{2}2)<2n(\lfloor lo{g}_2(n)\rfloor )$

$2(\lfloor lo{g}_2^2\rfloor +\lfloor lo{g}_2^3\rfloor +\lfloor lo{g}_2^4\rfloor +...+\lfloor lo{g}_2^{n-1}\rfloor )=2\ast \lfloor lo{g}_2^{(n-1)!}\rfloor <2\lfloor lo{g}_2^{n!}\rfloor$

$lo{g}_2^n!=\sum _{i=1}^{n}lo{g}_2^i\le \sum _{i=1}^{n}lo{g}_2^n=nlo{g}_2^n⟹O(nlo{g}_2^n)$

时间复杂度为$O(nlo{g}_{2}n)$

堆排序的最终复杂时间复杂度为$O(n)$+$O(nlo{g}_2^n)$ $⟹$ $O(nlo{g}_2^n)$

空间复杂度

算法只申请了几个固定的大小的空间来协助排序，空间复杂度为$O(1)$