一、总体逻辑：
1. 写一个 交换的函数swap 备用
2. 写一个 维护堆的性质的函数heapify 备用
3. 数组 -> 堆（不明白的别急，后面会详细解释）
4. 维护整个堆（看不懂别急别急别急）
5. 堆顶 和 堆底的最后一个元素 互换（不明白的也别急奥，后面会解释的详详细细，完完整整，明明白白）
6. 维护堆顶
！！！ 还要明白父节点与孩子节点的关系！！！：
1. 数组长度假设为 len：
最后一个的最小子树的父节点 = ( len - 1) / 2
2. 父节点假设下标为n：
左孩子节点的下标 = 2n + 1
右孩子节点的下标 = 2n + 2
二、解释：（是不是迫不及待想知道了呢！来啦来啦！）
1. 写一个交换函数：就是为了简化相同逻辑的代码，将重要的函数编写时尽可能的偏向于思维，而非繁琐的过程，因为c语言没有任何库可以调用，所以只能自己手写咯。
注意：要使用地址，才能正常的交换，否则只是给形参赋值了，并没有交换实际的
变量，所以后续能看到一个“&”，就是取其地址的意思
2. 写一个维护堆的性质的函数：
堆是什么呢？
堆就是由一个数组转为的一个完全二叉树，只不过对其有了一定的要求
为什么要维护堆呢？
因为一个重要的概念就是大顶堆。
什么是大顶堆呢？
大顶堆就是最大的元素在根节点，其孩子节点一定是比它小的
怎么维护堆呢？
就时刻依照大顶堆的性质，从最小的大顶堆开始维护，向左向上维护。且都要看一下它的下方是否满足
听不懂？ 上图！
其中每一个框里都是一个小堆，他们都要满足大顶堆的概念，就是将每个小
堆中元素最大的放在堆顶，且要向左向上维护
啥？不明白什么是向左向上维护？
根据这个图来说就是：橙 --> 蓝 --> 紫 --> 红
啥？不知道什么是堆顶？上图上图！
可看出，堆顶是相比较而言的！
3.数组 -> 堆：数组变成堆，依照树的层次遍历，什么是层次遍历呢？就是一层一层的遍历（好像说了些废话），上图！
4. 维护整个堆：就是使用调用前面编写的备用的函数咯，可以理解为从下往上进行1v1，赢的（数大的赢）就往上走，就当爹（变为父节点），所以最顶上的当然是最大的咯。
5. 堆顶 和 堆底的最后一个元素 元素互换：这个已经讲过咯，在最大的堆中，堆顶一定是最大的，将整个堆的堆顶与最后一个元素互换（就是将最大的元素放在最后，才能排序成 小->大）
6. 维护堆顶：为什么又要维护堆顶呢？因为堆底可一定不是第二大的呀，他还有个爹呢，所以它不遵循大顶堆的规则呀，所以要维护！
三、代码讲解：
1. 写一个 交换的函数swap 备用：
void swap(int *a, int *b)
{
int temp = *b;
*b = *a;
*a = temp;
}2. 写一个 维护堆的性质的函数heapify 备用：
形参：数组的地址 arr，数组长度 len，待维护节点的下标 i
思路：1.定义一个变量 largest 记录最大值，默认为最小子树的父节点的下标。
// 默认记录父节点的下标
int largest = i;2. 定义左孩子、右孩子，并计算，根据 一、总体逻辑 中的公式：
父节点假设下标为n：
左孩子节点的下标 = 2n + 1
右孩子节点的下标 = 2n + 2
// 父节点为代维护节点i，计算的左孩子
int lson = i * 2 + 1;
// 父节点为代维护节点i，计算的右孩子
int rson = i * 2 + 2;3.判断左右孩子和父节点哪个大，并用思路1定义的变量记录，若父节点大于左右孩子，则无需记录，因为 largest 默认了记录父节点的下标
// 判断父节点和孩子节点哪个大，并使用largest记录
// 左孩子在范围之内 且 左孩子的值更大时
if (lson < len && arr[largest] < arr[lson])
{
// 记录最大值的下标
largest = lson;
}
// 右孩子在范围之内 且 右孩子的值更大时
if (rson < len && arr[largest] < arr[rson])
{
// 记录右孩子的下标
largest = rson;
}4. 判断父节点是否为最大
若父节点为最大，则 largest 不会改变，为默认的父节点的下标，无
需做任何操作就符合大顶堆的性质
若父节点不为最大，即孩子中有一个大的，所以就要将大的元素放到
父节点，所以就需要递归维护更小的子树，此时的 largest 记录的是
刚从父节点下来的元素的下标，即待维护的下标（因为不知道他和
更小的子树之间的大小关系）
// 当父节点的值不为最大时，即使用largest记录了最大值的下标
if (largest != i)
{
// 将最大值放在父节点
swap(&arr[largest], &arr[i]);
// 递归维护更小的子树，此时largest记录了待维护节点的下标
heapify(arr, len, largest);
}以下逻辑将写在同一个函数中。为什么？因为上面的函数要多次调用，同样是备用的，真正的逻辑是在下面的这些代码：
3. 数组 -> 堆：
( len - 1 ) / 2 是 一、总体逻辑 底下总结的规律：
数组长度假设为 len：
最后一个的最小子树的父节点 = ( len - 1) / 2‘
代码在下面的 4.
4. 维护整个堆：
// 从最后一个最小子树的堆顶开始
for (i = (len - 1) / 2; i >= 0; i--)
{
// 维护从最后一个最小子树的堆顶，向左向上
heapify(arr, len, i);
}
5. 堆顶 和 堆底的最后一个元素 互换：
即将整个堆的堆顶与最后一个元素互换（就是将最大的元素放在最后，才能排序成 小->大）
代码在下面的 6.
6. 维护堆顶：
// 排序 -- 即将整个堆的堆顶与最后一个元素互换（就是将最大的元素放在最后，才能排序成 小->大 ）
// 然后删掉相连的线
// 从最后一个元素开始
for (i = len - 1; i >= 0; i--)
{
// 将堆的最后一个元素和堆顶元素交换，确定了堆顶元素的位置，但是此时堆顶不合法
swap(&arr[i], &arr[0]);
// 每次交换完已经确定了一个元素的位置，所以元素长度也是动态的，即i
// 维护堆顶的位置
heapify(arr, i, 0);
}四、代码附上：
#include <stdio.h>
void printArr(int *arr, int len)
{
for (int i = 0; i < len; i++)
printf("%d ", arr[i]);
printf("\n");
}
void swap(int *a, int *b)
{
int temp = *b;
*b = *a;
*a = temp;
}
/**
* 维护堆的性质
* @param arr 存储堆的数组
* @param len 数组长度
* @param i 待维护节点的下标
*/
void heapify(int *arr, int len, int i)
{
// 默认记录父节点的下标
int largest = i;
// 父节点为代维护节点i，计算的左孩子
int lson = i * 2 + 1;
// 父节点为代维护节点i，计算的右孩子
int rson = i * 2 + 2;
// 判断父节点和孩子节点哪个大，并使用largest记录
// 左孩子在范围之内 且 左孩子的值更大时
if (lson < len && arr[largest] < arr[lson])
{
// 记录最大值的下标
largest = lson;
}
// 右孩子在范围之内 且 右孩子的值更大时
if (rson < len && arr[largest] < arr[rson])
{
// 记录右孩子的下标
largest = rson;
}
// 当父节点的值不为最大时，即使用largest记录了最大值的下标
if (largest != i)
{
// 将最大值放在父节点
swap(&arr[largest], &arr[i]);
// 递归维护更小的子树，此时largest记录了待维护节点的下标
heapify(arr, len, largest);
}
// 当父节点的值为最大时，即堆无需维护，结束函数
}
/**
* 堆排序入口
* @param arr 存储堆的数组
* @param len 数组长度
*/
void heapSort_circulation(int *arr, int len)
{
int i;
// 建堆
// 从最后一个最小子树的堆顶开始
for (i = (len - 1) / 2; i >= 0; i--)
{
// 维护从最后一个最小子树的堆顶，向左向上
heapify(arr, len, i);
}
// 排序 -- 即将整个堆的堆顶与最后一个元素互换（就是将最大的元素放在最后，才能排序成 小->大 ）
// 然后删掉相连的线
// 从最后一个元素开始
for (i = len - 1; i >= 0; i--)
{
// 将堆的最后一个元素和堆顶元素交换，确定了堆顶元素的位置，但是此时堆顶不合法
swap(&arr[i], &arr[0]);
// 每次交换完已经确定了一个元素的位置，所以元素长度也是动态的，即i
// 维护堆顶的位置
heapify(arr, i, 0);
}
}
void main()
{
int arr1[] = {5, 6, 2, 9, 8, 7, 3, 1, 4};
int len = sizeof(arr1) / sizeof(int);
printf("排序前：\n");
printArr(arr1, len);
heapSort_circulation(arr1, len);
printf("排序后：\n");
printArr(arr1, len);
}