堆排序

顾名思义，堆排序就是利用堆的性质进行的选择排序

堆

堆是一棵顺序存储的完全二叉树
其中每个根结点的关键字都不大于其孩子结点的关键字，这样的堆称为小根堆。
其中每个根结点的关键字都不小于其孩子结点的关键字，这样的堆称为大根堆。

完全二叉树性质

设当前元素为数组的第i个元素，那么，
(1) 它的左孩子结点是：2i + 1;
(2) 它的右孩子结点是：2i + 2;
(3) 它的父结点是：(i-1) / 2;
(4)从下往上第一个非叶子节点：(length / 2) - 1;

算法思路

1. 构造初始堆(从由下至上第一个非叶子节点开始)；
2. 交换首尾元素；
3. 数组长度减一，把剩下的元素重新调整为大根堆；
4. 重复2、3直至剩下最后一个元素结束。

构造堆示意图

构造堆示意图

排序过程

复杂度