编程马拉松 Day05 堆、二叉堆、堆排序

堆

堆排序需要用到二叉堆，在开始之前，我们先来了解一下什么是二叉堆。

当二叉树满足满足如下条件时，我们说这个二叉树是堆有序的：

1. 每一个父结点的值都比它的子结点大（称为大顶堆）或小（称为小顶堆）
2. 子结点的大小与其左右位置无关

堆有序的二叉树，也可称为二叉堆。二叉堆是最常见的堆结构，因此也常将二叉堆直接称为堆，可以采用如下两种方式来表示二叉堆

1. 使用指针，二叉树的每个结点需存储三个指针，分别指向其父结点和两个子结点
2. 使用数组，对二叉树做层序遍历，按层级顺序放入数组中，根结点在数组索引0的位置存放，其子结点分别在索引1和2的位置，1和2个子结点分别在位置3、4和5、6中存放，以此类推

就排序来讲，其所需处理的数据较为连续，没有空隙，可用完全二叉树来表示。对于完全二叉树，采用数组的表示方法也更方便些，下图展示了采用数组实现的两个二叉堆。

二叉堆

对于数组实现的二叉堆，索引为k的结点的父结点的索引为(k-1)/2，它的子结点的索引分别为2k+1和2k+2。

堆有序化

以大顶堆为例，有序化的过程中我们会遇到两种情况

1. 在堆底加入一个较大元素时，我们需要由下至上恢复堆的顺序
2. 当将根结点替换为一个较小元素时，我们需要由上到下恢复堆的顺序

由下至上的堆有序化（上浮）

如果堆的有序状态因为某个结点变的比它的父结点更大而被打破，就需要通过将它与它的父结点交换来恢复堆有序。交换后，这个结点比它的两个子结点都大，但这个结点仍然可能比它现在的父结点更大。我们可以一遍遍的用同样的方式来将其向上移动，直到遇到一个比它更大的父结点或到达了堆的根结点，如下图所示。

由下至上的堆有序化（上浮）

上浮操作对应的代码如下

private void swim(Integer arr[], int k) {
    while(k > 0 && arr[(k - 1) / 2] < arr[k]) { //若k>0且索引为k的结点大于其父结点时，将该结点与其父结点交换
        swap(arr, k, (k - 1) / 2);
        k = (k - 1) / 2;
    }
}

由上至下的堆有序化（下沉）

如果堆的有序状态因为某个结点变的比它的某个子结点更小而被打破，就需要通过将它和它的子结点中较大者交换位置来恢复堆有序。交换可能会在子结点处继续打破堆的有序状态，此时可以采用相同的方式，将结点向下移动直到它的子结点都比它小或是到达了堆的底部，如下图所示。

由上至下的堆有序化（下沉）

下沉操作对应的代码如下

private void sink(Integer arr[], int k) {
    while(2 * k + 1 <= arr.length - 1) {//若k存在子结点，则进入循环
        int j = 2 * k + 1; //获取k的第一个子结点
        if (j < arr.length - 1 && arr[j] < arr[j + 1]) {//若存在两个子结点，则找到其中较大的子结点
            j++;
        }
        if (arr[j] > arr[k]) {//若k的较大子结点比k大，则交换它们的位置
            swap(arr, j, k);
            k = j;
        }
    }
}

堆排序

在介绍完堆的数据结构和操作方式后，我们来看堆排序是如何进行的。

堆的构造

1. 将原数组看做堆的话，则最后一个分支结点（含有子结点的结点）在原数组中的索引为 (n-1)/2 -1
2. 从(n-1)/2-1向前依次执行下沉操作，从而得到堆有序的数组

堆初始化

堆的排序

1. 取出堆的根结点，与数组最后一个元素交换。交换后堆有序状态可能会被打破，需要在新的根结点进行下沉操作，使其恢复为堆有序状态。此时数组中最大(大顶堆)/最小(小顶堆)的值存放在数组末位，除它以外的最 大/小 值位于堆顶。
2. 从数组中排除最后一个元素，重复步骤2，直到数组中的元素全部排除时，完成排序

堆排序

public static void heapSort(Integer arr[]) {
    int n = arr.length;
    //堆的构造,对每一个含有孩子的结点做下沉操作,得到大顶堆
    for (int i = (n-1) /2 -1; i >= 0; i--) {
        heapSink(arr, i, n);
    }
    printArr(arr, "大顶堆");
    for (int i = n - 1; i > 0; i--) {
        swap(arr, 0, i);
        heapSink(arr, 0, i);
    }
    printArr(arr, "堆排序");

}

public static void heapSink(Integer arr[], int i, int length) {
    while(2 * k + 1 <= length - 1) {//若k存在子结点，则进入循环
        int j = 2 * k + 1; //获取k的第一个子结点
        if (j < length - 1 && arr[j] < arr[j + 1]) {//若存在两个子结点，则找到其中较大的子结点
            j++;
        }
        if (arr[j] > arr[k]) {//若k的较大子结点比k大，则交换它们的位置
            swap(arr, j, k);
            k = j;
        }
    }
}

堆排序动态图

堆排序动态图

小结

堆排序算法也是一种选择排序算法，整体由堆的构建、堆的交换与下沉两个步骤组成。其中堆的构建需要比较(n-1)/2-1次下沉，每次下沉至多交换一次，时间复杂度为O(n)；堆的交换与下沉中需交换n次，下沉依次需要执行\log_2(n-1),log_2(n-2)...1次交换，近似为Nlog_2N。因此堆排序的时间复杂度为O(N\log_2N)