目录
前言
上期我们对简单选择排序进行了详细的介绍，我们发现简单选择排序虽然简单，但是它的复杂度还是比较高，那么今天我们来介绍它的改进版—堆排序。
什么是堆排序
991年的计算机先驱奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德(Robert W．Floyd）和威廉姆斯(J．Williams）在1964年共同发明了著名的堆排序算法。堆排序（是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
堆排序的实现
基本思想
创建一个堆
把堆首和最后一个元素互换；
把堆的尺寸缩小 1，并继续进行堆排序，目的是把新的数组顶端数据调整到相应位置；
重复步骤 2，直到堆的尺寸为 1。
具体的代码实现
#include <stdio.h> //交换两个元素 传的是地址，就用指针接收 void swap(int *a, int *b) { int tmp = *a; *a = *b; *b = tmp; } //变成堆 void heapify(int* arr, int n, int i) { //父亲 int dad = i; //左孩子 int lson = 2 * i + 1; //右孩子 int rson = 2 * i + 2; //大于父亲就交换 注意不能越界 if (lson< n && arr[dad] < arr[lson]) { dad = lson; } if (rson < n && arr[dad] < arr[rson]) { dad = rson; } if (dad != i) { swap(&arr[i], &arr[dad]); //交换后可能会破坏堆的性质 用递归再进行堆排列 heapify(arr, n, dad); } else return; } //堆排序 void heap_sort(int* arr, int n) { int i = 0; //建堆 从最后一个父亲开始 for (i = (n - 1 - 1) / 2; i >= 0; i--) { heapify(arr, n, i); } //排序 for (i = n - 1; i > 0; i--) { //交换最后一个和第一个 swap(&arr[i], &arr[0]); //再将它们变成大顶堆 heapify(arr, i, 0); } } int main() { //待排序元素 int arr[] = { 2,34,5,1,0,5,6,3,2,17,4,32,56 }; //求元素个数 int sz = sizeof(arr) / sizeof(arr[0]); //堆排序 heap_sort(arr, sz); int i = 0; //打印 for (i = 0; i < sz; i++) { printf("%d ", arr[i]); } return 0; }
基本原理
这里有几个知识点需要说明：
大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列
小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列
我们代码中用的就是大顶堆。这里的大顶堆用的就是完全二叉树，什么是完全二叉树呢？
完全二叉树
二叉树是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。二叉树特点是每个节点最多只能有两棵子树，且有左右之分 。
完全二叉树就是设二叉树的深度为h，除第 h 层外，其它各层的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。一棵二叉树至多只有最下面的一层上的结点的度数可以小于2，并且最下层上的结点都集中在该层最左边的若干位置上，而在最后一层上，右边的若干结点缺失的二叉树，则此二叉树成为完全二叉树。
堆排序的性能
初始化建堆的时间复杂度为O (n)，排序重建堆的时间复杂度为nlog (n)，所以总的时间复杂度为O (n+nlogn)=O (nlogn)。另外堆排序的比较次数和序列的初始状态有关，但只是在序列初始状态为堆的情况下比较次数显著减少，在序列有序或逆序的情况下比较次数不会发生明显变化。复杂度的计算过程：
假设目标堆是一个满堆，即第 k 层节点为 2ᵏ。输入数组规模为 n, 堆的高度为 h, 那么 n 与 h 之间满足 n=2ʰ⁺¹ - 1，可化为 h=log₂(n+1) - 1。 (层数 k 和高度 h 均从 0 开始，即只有根节点的堆高度为0，空堆高度为 -1)。
建堆过程中每个节点需要一次下滤操作，交换的次数等于该节点到叶节点的深度。那么每一层中所有节点的交换次数为节点个数乘以叶节点到该节点的深度（如第一层的交换次数为 2⁰ · h，第二层的交换次数为 2¹ · (h-1)，如此类推）。从堆顶到最后一层的交换次数 Sn 进行求和：
Sn = 2⁰ · h + 2¹ · (h - 1) + 2² · (h - 2) + ...... + 2ʰ⁻² · 2 + 2ʰ⁻¹ · 1 + 2ʰ · 0
把首尾两个元素简化，记为①式：
①: Sn = h + 2¹ · (h - 1) + 2² · (h - 2) + ...... + 2ʰ⁻² · 2 + 2ʰ⁻¹
对①等于号左右两边乘以2，记为②式：
②: 2Sn = 2¹ · h + 2² · (h - 1) + 2³ · (h - 2) + ...... + 2ʰ⁻¹ · 2 + 2ʰ
那么用②式减去①式，其中②式的操作数右移一位使指数相同的部分对齐（即错位相减法）：
化简可得③式：
③ = Sn = -h + 2¹ + 2² + 2³ + ...... + 2ʰ⁻¹ + 2ʰ
对指数部分使用等比数列求和公式：Sn=a1×(1−qn)1−qSn=\frac{a_{1}\times\left( 1-q^{n} \right)}{1-q}
在这个等比数列中，a1=2, q=2，则③式为：
对指数部分使用等比数列求和公式：Sn=a1×(1−qn)1−qSn=\frac{a_{1}\times\left( 1-q^{n} \right)}{1-q}
在这个等比数列中，a1=2, q=2，则③式为：
在前置条件中已得到堆的节点数 n 与高度 h 满足条件 n=2ʰ⁺¹ - 1（即 2ʰ⁺¹=n+1） 和 h=log₂(n+1) - 1，分别代入④式中的 2ʰ⁺¹ 和 h，因此：
Sn=(n+1)−(log2(n+1)−1+2)Sn=\left( n + 1 \right) - \left( log_{2}\left( n+1 \right) - 1 + 2 \right)
化简后为：
Sn = n - log₂(n + 1)
因此最终可得为 O(n).
堆排序的改进
因为大多数重新插入堆的元素会直接加入到堆底，发现我们可以免去检查元素是否到达正确位置来节省时间。也就是直接提升较大的子结点直至到达堆底，然后再使元素上浮 🔝 到正确位置。这样几乎可以将比较的次数减半，接近了对随机数组进行归并排序所需要的比较次数。不过需要额外的空间，在实际应用中只会当比较操作代价高时较高时才会使用。改进方法：
将数据初始化为大顶堆，交换第一个和最后一个元素，这里是不变的
重新构造大顶堆是，首先让第一个元素下降h/2的高度（h 为堆的高度）
下降了h/2层后判断这个元素与它的父节点谁大，如果父节点大继续下沉，下沉的结束条件为h=0 如果父节点小，表明第一个元素下沉时走过头了，然后要往回走，进行上浮操作，上浮操作是肯定能够找到第一个元素的最终位置的
循环n-1次程序运行完成。
代码：
void HeapSort_Floyd(void *arr, int n, int size) { for (int k = n / 2; k != 0; --k) Sink(arr, k, n, size); while (n != 1) { void * temp = malloc(size); memcpy(temp, arr + (n - 1) * size, size); Cover(arr, n--, 1, size); int k = 1; while (2 * k <= n) { int j = 2 * k; if (2 * k < n && LessArr(arr, j, j + 1, size)) ++j; Cover(arr, k, j, size); k = j; } memcpy(arr + (k - 1) * size, temp, size); Swim(arr, k, size); free(temp); } }
