排序(10) 堆排序(非泛型)

发表于 | 分类于 | 阅读次数:

堆排序是把数组看作堆，第i个结点的孩子结点为第 2i + 1和 2i + 2个结点（不超出数组长度前提下），堆排序的第一步是建堆，然后是取堆顶元素然后调整堆。建堆的过程是自底向上不断调整达成的，这样当调整某个结点时，其左节点和右结点已经是满足条件的，此时如果两个子结点不需要动，则整个子树不需要动，如果调整，则父结点交换到子结点位置，再以此结点继续调整。

二叉堆回顾

最大（小）堆

二叉堆本质上是一种完全二叉树，它分为两个类型：
1.最大堆
2.最小堆

完全二叉树定义：如果一棵二叉树的每一层都是满的，或者最后一层可以不填满并且最后一层的叶子都是靠左放置的，这可二叉树是完全的。

堆排序使用的是二叉堆（binary heap），二叉堆是一棵具有如下属性的二叉树：
形状属性：它是一棵完全二叉树。
堆属性：
什么是最大堆呢？最大堆任何一个父节点的值，都 大于等于它左右孩子节点的值。
什么是最小堆呢？最小堆任何一个父节点的值，都 小于等于它左右孩子节点的值。

二叉堆的根节点叫做堆顶。

最大堆和最小堆的特点，决定了在最大堆的堆顶是整个堆中的 最大元素；最小堆的堆顶是整个堆中的 最小元素。

堆的三种操作

对于二叉堆，如下有几种操作：

  • 插入节点，二叉堆的节点插入，插入位置是完全二叉树的最后一个位置。
  • 删除节点，二叉堆的节点删除过程和插入过程正好相反，所删除的是处于堆顶的节点。
  • 构建二叉堆，也就是把一个无序的完全二叉树调整为二叉堆。
    这几种操作都是基于堆的自我调整。

构建二叉堆

构建二叉堆，也就是把一个无序的完全二叉树调整为二叉堆，本质上就是让所有非叶子节点依次下沉。

堆的代码实现

二叉堆虽然是一颗完全二叉树，但它的存储方式并不是链式存储，而是顺序存储。换句话说，二叉堆的所有节点都存储在数组当中。
数组中，在没有左右指针的情况下，如何定位到一个父节点的左孩子和右孩子呢？

可以依靠数组下标来计算。假设父节点的下标是parent，那么它的左孩子下标就是 2parent+1；它的右孩子下标就是 2parent+2 。

堆的上浮和下浮调整操作
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
public class HeapOperator {
    // 上浮调整 arr为待调整的堆
    public static void upAdjust(int[] arr) {
        int childIndex = arr.length - 1;
        int parentIndex = (childIndex - 1) / 2;
        // 用tmp保存插入的叶子节点值，用于最后的赋值
        int tmp = arr[childIndex];
        while (childIndex > 0 && tmp < arr[parentIndex]) {
            // 无须真正交换，单向赋值即可
            arr[childIndex] = arr[parentIndex];
            childIndex = parentIndex;
            parentIndex = (parentIndex - 1) / 2;
        }
        arr[childIndex] = tmp;
    }

    // 下沉调整，arr为待调整的堆，parentIndex为要下沉的父节点，length为堆的有效大小
    public static void downAdjust(int[] arr, int parentIndex, int length) {
        int tmp = arr[parentIndex];
        int childIndex = 2 * parentIndex + 1;
        while (childIndex < length) {
            // 如果有右孩子，且右孩子小于左孩子的值，则定位到右孩子
            //  arr[childIndex + 1] > arr[childIndex]
            if (childIndex + 1 < length && arr[childIndex + 1] < arr[childIndex]) {
                childIndex++;
            }
            // 如果父节点小于任何一个孩子的值，直接跳出
            // if (tmp > arr[childIndex]) 
            if (tmp <= arr[childIndex]) 
                break;
            // 无需真正交换，单向赋值即可
            arr[parentIndex] = arr[childIndex];
            parentIndex = childIndex;
            childIndex = 2 * childIndex + 1;
        }
        arr[parentIndex] = tmp;
    }

    //构建堆 arr为待调整的堆
    public static void buildHeap(int[] arr) {
        // 从最后一个叶子节点开始，依次下沉调整
        for (int i = arr.length / 2; i >= 0; i--) {
            downAdjust(arr, i, arr.length - 1);
        }
    }

    public static void main(String[] args) {
        int[] arr = { 1, 3, 2, 6, 5, 7, 8, 9, 10, 0 };
        upAdjust(arr);
        System.out.println(Arrays.toString(array));
        array = new int[] { 7, 1, 3, 10, 5, 2, 8, 9, 6 };
        buildHeap(array);
        System.out.println(Arrays.toString(array));
    }
}

代码中有一个优化的点，就是父节点和孩子节点做连续交换时，并不一定要真的交换，只需要先把交换一方的值存入temp变量，做单向覆盖，循环结束后，再把temp的值存入交换后的最终位置。

堆排序

我们每一次删除旧堆顶，调整后的新堆顶都是大小仅次于旧堆顶的节点。那么我们只要反复删除堆顶，反复调节二叉堆，所得到的集合就成为了一个有序集合。

二叉堆和最大堆的特性：

  1. 二叉堆本质上是一种完全二叉树
  2. 最大堆的堆顶是整个堆中的最大元素

当我们删除一个最大堆的堆顶（并不是完全删除，而是替换到最后面），经过自我调节，第二大的元素就会被交换上来，成为最大堆的新堆顶。

由此，我们可以归纳出堆排序算法的步骤：

  1. 把无序数组构建成二叉堆。
  2. 循环删除堆顶元素，移到集合尾部，调节堆产生新的堆顶。

堆排序代码实现

堆排序实现
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
public class HeapSort{
    /**
     * 下沉调整
     * @param arr          待调整的堆
     * @param parentIndex  要下沉的父节点
     * @param length       堆的有效大小
     */
    public static void downAdjust(int[] arr, int parentIndex, int length) {
        int tmp = arr[parentIndex];
        int childIndex = 2 * parentIndex + 1;

        while (childIndex < length) {
            // 如果有右孩子，且右孩子大于左孩子的值，则定位到右孩子
            if (childIndex + 1 < length && arr[childIndex + 1] > arr[childIndex]) {
                childIndex++;
            }
            //如果父节点大于等于任何一个孩子的值，直接跳出
            if (tmp >= arr[childIndex]) 
                break;
            //无需真正交换，单向赋值即可
            arr[parentIndex] = arr[childIndex];
            parentIndex = childIndex;
            childIndex = 2 * childIndex + 1;
        }
        arr[parentIndex] = tmp;
    }

    //堆排序 arr为待调整的堆
    public static void heapSort(int[] arr) {
        // 1. 把无需数组构建成二叉堆
        for (int i = arr.length/2 - 1; i >= 0; i--) {
            downAdjust(arr, i, arr.length);
        }
        System.out.println(Arrays.toString(arr));

        // 2.循环删除顶端元素，移到数组尾部，调整堆产生新的堆顶
        for (int i = arr.length - 1; i > 0; i--) {
            //最后一个元素和第一个元素进行交换
            int tmp = arr[i];
            arr[i] = arr[0];
            arr[0] = tmp;
            // 下沉调整最大堆
            downAdjust(arr, 0, i);
        }
    }

    public static void main(String[] args) {
        int[] arr = { 1, 3, 2, 6, 5, 7, 8, 9, 10, 0 };
        heapSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

堆排序的时间空间复杂度

算法复杂度：
时间复杂度（平均）： O(nlogn)
时间复杂度（最坏）： O(nlogn)
时间复杂度（最好）： O(nlogn)

空间复杂度： O(1)
堆排序是不稳定的排序算法。

堆排序的空间复杂度毫无疑问是O(1)，因为没有开辟额外的集合空间。

对于时间复杂度：
二叉堆的节点下沉调整（downAdjust 方法）是堆排序算法的基础，这个调节操作本身的时间复杂度是多少呢？
假设二叉堆总共有n个元素，那么下沉调整的最坏时间复杂度就等同于二叉堆的高度，也就是O（logn）。

我们再来回顾一下堆排序算法的步骤：

  1. 把无序数组构建成二叉堆。
  2. 循环删除堆顶元素，移到集合尾部，调节堆产生新的堆顶。

第一步，把无序数组构建成二叉堆，需要进行n/2次循环。每次循环调用一次 downAdjust 方法，所以第一步的计算规模是 n/2 * logn，时间复杂度 O（nlogn）。

第二步，需要进行n-1次循环。每次循环调用一次 downAdjust 方法，所以第二步的计算规模是 （n-1） * logn ，时间复杂度 O（nlogn）。

两个步骤是并列关系，所以整体的时间复杂度同样是 O（nlogn）。

0%