堆排序

堆（Heap）

二叉堆本质上是一种完全二叉树，分为最大堆和最小堆两个类型。在最大堆中，任何一个父结点的值都大于等于它左右孩子结点的值。在最小堆中，任何一个父结点的值都小于等于它左右孩子结点的值。

二叉堆的根结点称为堆顶，在最大堆中堆顶是整个堆中的最大元素，在最小堆中堆顶是整个堆中的最小元素。

在二叉堆中插入结点、删除结点、构造二叉堆的操作都基于堆的自我调整。

二叉堆虽然是一棵完全二叉树，但它的存储方式并不是链式存储，而是顺序存储。数组中，通过下标可以定位到结点的左右孩子，假设父结点的下标是parent，那么它的左孩子下标为2 * parent + 1、右孩子下标为2 * parent + 2。

插入结点

二叉堆的插入操作可以看成是结点上浮，当在堆中插入一个结点时，必须满足完全二叉树的标准，那么被插入结点的位置是完全二叉树的最后一个位置。在最大堆中，如果新结点的值大于它的父结点的值，则让新结点上浮，即和父结点交换位置。

堆的插入时间复杂度取决于树高为$O(logn)$。

例如在大顶堆{20, 15, 2, 14, 10}中插入21：

将新元素21与其父结点2比较，因为21 > 2，将21和2的位置交换：

因为21 > 20，将21与20的位置交换：

删除结点

二叉堆的删除操作总是从堆的根结点删除元素。根结点被删除之后为了能够保证该树还是一棵完全二叉树，需要将完全二叉树的最后一个结点补到根结点的位置，让其继续符合完全二叉树的定义。二叉堆的删除结点操作可以看作是结点下沉。在最大堆中，如果新堆顶元素小于它的左右孩子中较大的那个结点，则与它的较大的子结点交换位置。

堆的删除时间复杂度取决于树高为$O(logn)$。

例如删除大顶堆的堆顶元素20：

移动最后一个结点到堆顶，使其满足二叉树的性质：

将堆顶元素1与其子结点比较，因为15 > 2，交换较大子结点15与1的位置：

继续将元素1与其子结点比较，因为14 > 10，交换较大子结点14与1的位置：

构建二叉堆

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

例如将一个无序的完全二叉树构建成最小堆：

首先从最后一个非叶子结点开始，结点10下沉：

接着处理倒数第二个非叶子结点，结点3下沉：

倒数第三个非叶子结点1无需移动。

最后处理倒数第四个非叶子结点7下沉：

最终一棵无序完全二叉树就调整成了一个最小堆。

堆排序（Heap Sort）

有了二叉堆的构建、删除和自我调节，实现堆排序就是水到聚成了。当删除一个最大堆的堆顶后（并不是完全删除，而是替换到堆的最后面），经过自我调节，第二大的元素就会被交换上来，成为最大堆的新堆顶。

首先将待排序数组构建成大顶堆：

移除堆顶元素（与最后元素交换）：

将新的堆顶元素进行下沉，重新调整为大顶堆：

只要反复删除堆顶，反复调节二叉堆，所得到的集合就成为了一个有序集合。

堆排序

四种语言均使用原稿dsa/code中的堆排序示例；每次heapify只处理仍在堆内的区间。

#include <stdio.h>

typedef int T;

#define swap(x, y)  \
    {               \
        T temp = x; \
        x = y;      \
        y = temp;   \
    }

static void heapify(T *arr, int index, int n) {
    int child_index = 2 * index + 1;
    while (child_index < n) {
        if (child_index + 1 < n && arr[child_index + 1] > arr[child_index]) {
            child_index++;
        }
        if (arr[index] >= arr[child_index]) {
            break;
        }
        swap(arr[index], arr[child_index]);
        index = child_index;
        child_index = 2 * index + 1;
    }
}

/**
 * Heap Sort (original v1.0)
 */
T *heap_sort(T *arr, int n) {
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, i, n);
    }

    for (int i = n - 1; i > 0; i--) {
        swap(arr[0], arr[i]);
        heapify(arr, 0, i);
    }

    return arr;
}

int main() {
    int arr[] = {5, 8, 6, 3, 9, 2, 7, 4, 10};
    int n = sizeof(arr) / sizeof(arr[0]);

    heap_sort(arr, n);
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

堆排序的空间复杂度为$O(1)$，因为算法并没有开辟额外的集合空间。

至于时间复杂度，假设二叉堆总共有n个元素，那么下沉调整的最坏时间复杂度就等同于二叉堆的高度$O(logn)$。

堆排序的算法步骤分为两部分：

1. 把无序数组构建成二叉堆：从最后一个非叶子结点开始自底向上下沉调节。多数结点靠近叶子，下沉距离很短，所有结点的调整次数之和为$O(n)$，因此此步骤的时间复杂度为$O(n)$。

2. 循环删除堆顶元素，移到数组尾部，调节堆产生新堆顶：进行n - 1次循环，每次循环进行一次下沉调节，因此此步骤的计算规模为$(n-1) * logn$，时间复杂度为$O(nlogn)$。

综合堆排序的两个步骤，整体时间复杂度为$O(nlogn)$。