排序算法-堆排序

一、前提

堆排序是一种给数组排序的算法，最后的结果是一个有序的数组。之所以叫堆排序是用了堆的逻辑结构。

二、理解要点

1. 堆（大堆、小堆）
2. 完全二叉树的特点
3. 构建初始堆
4. 根节点输出
5. 从下到上的构建初始堆，从上到下的调整根节点

三、要点解释

堆

堆是具有以下性质的完全二叉树：

• 大顶堆：每个结点的值都大于或等于其左右孩子结点的值
• 小顶堆：或者每个结点的值都小于或等于其左右孩子结点的值

完全二叉树的特点

• 除了最下面一层，其余每层的节点数都是满的
• 用数组来存储的话，第i个节点的左子节点为2i+1,右子节点为2i+2
• 最后一个非叶子节点的index为length/2-1(注：其左子节点为n-1，也就是最后一个节点，所以index后面的节点都没有子节点了）

构建初始堆（以大堆为例）

• 将数组的顺序调整至符合大堆的条件
• 意义：当初始堆构造完成之后，后面的在将根节点输出之后只需要调整根节点就行而无需调整整个堆

根节点输出（以大堆为例）

• 在初始堆构建完成之后，根节点就是整个数组最大的数，将其与数组最后一个交换，这样就将数组的最大值放到了合适的位置
• 在根节点交换位置之后逻辑堆的根节点又不符合规则了，然后继续从下往上的调整根节点的位置，然后重复根节点的交换

从下到上的构建初始堆，从上到下的调整根节点

• 在构建堆时，要确保底层的节点符合堆的规则才能保证上层节点符合堆的规则
• 当初始堆构建完成之后，整个堆都满足上层大下层小（以大堆为例）的规则，当根节点置换输出之后，只有根节点不满规则，所以只需要从上到下的调整根节点的值就行

排序过程和代码实现可以参考这篇文章：https://www.cnblogs.com/chengxiao/p/6129630.html