堆排序

发表于 | 更新于 | 分类于

本篇简单讲述一下堆和堆排序

img

堆

堆分为堆分为最大堆和最小堆，其实就是完全二叉树，是一种经过排序的完全二叉树。

  • 最大堆要求节点的元素都要不小于其孩子
  • 最小堆要求节点元素都不大于其左右孩子
  • 两者对左右孩子的大小关系不做任何要求

完全二叉树

若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。

完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。

一棵二叉树至多只有最下面的两层上的结点的度数可以小于2，并且最下层上的结点都集中在该层最左边的若干位置上，则此二叉树成为完全二叉树。

特点：叶子结点只可能在最大的两层上出现,对任意结点，若其右分支下的子孙最大层次为L，则其左分支下的子孙的最大层次必为L 或 L+1。

堆排序

堆排序是一种树形选择排序，在排序过程中，将待排序多的记录r[1..n]看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系，在当前无序的序列中选择关键字最大（或最小）的记录。

基本思想
  1. 将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区。
  2. 将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn)。
  3. 由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。

堆排序过程的核心就是先初始化大根堆，将最大数（堆顶）放到堆的最后一个，堆长度-1，继续调整成大根堆，直至有序序列为length-1。

注意：

在初始化大跟堆时，是从最后一个有子节点开始向上调整到最大堆。而堆顶元素与堆最后一个数交换后，需要再次调整为大根堆

，此时是从上往下调整的。

不管是初始大顶堆的从下往上调整，还是堆顶堆尾元素交换，每次调整都是从父节点、左孩子节点、右孩子节点三者中选择最大者跟父节点进行交换，交换之后都可能造成被交换的孩子节点不满足堆的性质，因此每次交换之后要重新对被交换的孩子节点进行调整。

动画演示

图片来源：https://mp.weixin.qq.com/s/vn3KiV-ez79FmbZ36SX9lg

堆排序

代码实现
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
public class HeapSort {
    public static void heapSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }

        for (int i = 0; i < arr.length; i++) {
            heapInsert(arr, i);
        }
        int size = arr.length;

        // 将堆顶元素调整到最后
        swap(arr, 0, --size);
        //继续调整大根堆
        while (size > 0) {
            heapify(arr, 0, size);
            swap(arr, 0, --size);
        }
    }

    // 建立大根堆
    public static void heapInsert(int[] arr, int index) {
        while (arr[index] > arr[(index - 1) / 2]){  // (index -1) / 2 表示 index 的根结点
            swap(arr, index, (index - 1) / 2);  // 如果当前结点的值比根结点的值大，则交换
            index = (index - 1) / 2; // 继续往下比较
        }
    }

    // 调整大根堆
    public static void heapify(int[] arr, int index, int size) {
        // index * 2 + 1 当前结点的左孩子， + 2  为右孩子
        int left = index * 2 + 1;
        while (left < size) {
            // left + 1 < size 右孩子不越界
            // 左孩子和右孩子谁大，谁的下标作为largest
            int largest = left + 1 < size && arr[left + 1] > arr[left] ? left + 1 : left;

            // 我和孩子谁大，谁的下标作为largest
            largest = arr[largest] > arr[index] ? largest : index;
            // 最大是自己， 则结束下沉
            if (largest == index) {
                break;
            }
            // 不是，则继续下沉
            swap(arr, largest, index);
            index = largest;
            left = index * 2 + 1;
        }
    }

    // 交换方法
    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}
时间复杂度

堆排序的运行时间主要耗费在建初堆和调整堆时进行的反复“筛选”上。

在构建堆(初始化大顶堆)的过程中，完全二叉树从最下层最右边的非终端结点开始构建，将它与其孩子进行比较和必要的互换，对于每个非终端结点来说，其实最多进行两次比较和一次互换操作，因此整个构建堆的时间复杂度为:$O(n)$。大概需进行n/2 * 2 = n次比较和n/2次交换。

在正式排序时，n个结点的完全二叉树的深度为$⌊O(log_2n)⌋+1$，并且有n个数据则需要取n-1次调整成大顶堆的操作，每次调整成大顶堆的时间复杂度为$O(log2n)$。

初始化建堆的时间复杂度为$O(n)$，排序重建堆的时间复杂度为$O(log_2n)$，所以总的时间复杂度为$O(n+log_2n)=O(log_2n)O(n+log_2n)=O(log_2n)$。另外堆排序的比较次数和序列的初始状态有关，但只是在序列初始状态为堆的情况下比较次数显著减少，在序列有序或逆序的情况下比较次数不会发生明显变化。

实验研究表明，平均性能接近于最坏性能。

空间复杂度

堆排序数据交换时需要一个辅助空间，故空间复杂度是$O(1)$。

算法特点
  1. 是不稳定的排序
  2. 只能用于顺序结构，不能用于链式结构
  3. 初始建堆所需要的比较次数较多，因此记录数较少时不宜采用。堆排序在最坏情况下时间复杂度为$O(nlog_2n)$

参考

博客园：堆排序详解-前程明亮

0%