堆排序

百度百科：

堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆，是完全二叉树。

完全二叉树： 除了最后一层之外的其他每一层都被完全填充，并且所有结点都保持向左对齐。

简单来说：堆排序是将数据看成是完全二叉树、根据完全二叉树的特性来进行排序的一种算法

• 最大堆要求节点的元素都要不小于其孩子，最小堆要求节点元素都不大于其左右孩子

• 那么处于最大堆的根节点的元素一定是这个堆中的最大值

这里我们讨论最大堆：当前每个父节点都大于子节点

完全二叉树有个特性：左边子节点位置 = 当前父节点的两倍 + 1，右边子节点位置 = 当前父节点的两倍 + 2

现在我们有一个完全二叉树：左子树和右子树都符合最大堆-->父>子

但是我们会发现：根元素所在的数并不符合，明显的是：1是小于7的

将7和1对调，发现1还是小于5，又将5和1对调，于是我们第一次的建堆操作就完成了

接下来，剩下的数不断进行建堆，交换就可以完成我们的堆排序了