堆的结构（堆排序算法详解）

堆排序算法

堆排序（Heap sort）算法，是将数据看成近似完全二叉树结构，并根据完全二叉树的特性来进行排序的一种算法。完全二叉树要求每个结点的值都大于等于其左右子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。

堆排序就是把先将父节点的最大数取出，并构建最大堆，再将堆继续调整为最大堆，再次将堆顶的最大数取出，这个过程持续到剩余数只有一个时结束。堆排序的平均时间复杂度为 O(n log2 n)，空间复杂度：O(1)，稳定性：不稳定。

主要步骤是：

首先数据按照二叉数来看待，将其下标与二叉树节点对应起来；构建最大堆（Build-Max-Heap），将堆所有数据重新排序，使其成为最大堆，并且冒出最大数；堆排序(Heap-Sort)，从最后一个子节点开始遍历，并将根节点与其交换，也就是移除第一个数据的根节点，并做最大堆调整的递归调用，直到排序完成。

堆排序算法执行过程分析：

待排序数组：[7, 11, 9, 10, 12, 13, 8]

下标对应: 0 1, 2, 3, 4, 5, 6

二叉树结构与数组的关系如下：

堆与数组关系

根据以上位置关系，我们可以传入任意数组下标i，则可以得到父节点位置parent = (i-1) / 2取整，left = i * 2 + 1，right = i * 2 + 2。

遍历父节点，构建大顶堆，取出最大数，得到结果如下：

构建大顶堆，取出最大数

从子节点开始排序，置换顶根节点与子节点，并继续构建大顶堆：

将子节点与根节点交换且保持大顶堆

子节点排序完成，则堆排序完成，结果如下：

排序完成的大顶堆

堆排序算法代码如下：

JS代码版本

堆排序JS版 1/2

堆排序JS版 2/2

构建大顶堆的非递归方法

堆排序构建大顶堆非递归写法

非递归理解起来不如递归，但本质上是一模一样的，性能没有什么差别。

Python代码版本

堆排序Python版 1/2

堆排序Python版 2/2

Java代码版本

堆排序Java版 1/2

堆排序Java版 2/2

C代码版本

堆排序C语言版 1/4

堆排序C语言版 2/4

堆排序C语言版 3/4

堆排序C语言版 4/4

TypeScript代码版本

堆排序TS版 1/3

堆排序TS版 2/3

堆排序TS版 3/3

总结

堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。

堆排序的基本过程是：将待排序序列看成是一个完全二叉树，再去基于父节点构造成一个大顶堆，也就是将整个序列的最大值冒出到堆顶的根节点。然后将末尾节点与根节点进行交换，此时末尾就为最大值。然后将剩余的n-1个元素按照大顶堆规则进行构建，这样会将根节点不断冒出并交换到末尾的位置。依此遍历全部子节点，便把最大数逐个放在末尾，从而得到有序数列。