【数据结构】C语言排序方法——堆排序详解！_c语言二叉树堆排序

堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

对于堆的操作通常需要以下3个步骤：

最大堆调整（Max Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点

创建最大堆（Build Max Heap）：将堆中的所有数据重新排序

堆排序（HeapSort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算。

C代码实现：

代码看起来比较抽象，将代码运行时数据交换的过程打印出来，然后结合二叉树的图形来分析，就会比较好理解了。 代码运行过程中数据交换过程如下：

为了方便观看这里使用二叉树图形生成软件，通过二叉树图形来观察数据交换过程。 二叉树图形生成使用的是一个在线生成网站：mshang.ca/syntree 后面所有的二叉树图形都使用此软件生成。

代码一开始首先打印出原始数据

数组元素 0 8 1 5 4 3 7 9 2 6 将这10个数据在网站上使用公式生成二叉树的图表，软件界面如下：

首先将数组从上至下按顺序排列，转换成二叉树。

公式： 0[8 [5 9[2]][4[6]]] [1[3] [7 ]]]

生成二叉树图表：

转换成二叉树之后，需要让这个无序堆变成最大堆，也就是每个堆都实现父节点的值大于任何一个子节点值。 从最后一个堆开始，依次比较父节点和子节点的值，如果子节点值大于父节点值，就需要交换。

创建最大堆: 6为最后一个子节点，所以从6开始依次和父节点比较，如果子节点大于父节点，就需要交换子节点和父节点的位置。 从设备树图形中可以看出，子节点6大于父节点4，所以需要交换子节点的父节点的位置。

公式：0[8 [5 9[2]][6[4]]] [1[3] [7 ]]]

交换 6 和4

6交换完成后，接下来依次向前比较其他子节点，6前面的节点是2,2小于父节点5，继续向前查找子节点9,子节点9大于父节点5，所以就交换9和5的位置。

公式：0[8 [9 5[2]][6[4]]] [1[3] [7 ]]]

交换9