堆排序算法利用堆的结构来执行快速排序。
为了实现从最低到最高排序，堆排序首先将未排序的数组转换为最大堆，以便数组中的第一个元素最大。
假设要排序的数组是：
[ 5, 13, 2, 25, 7, 17, 20, 8, 4 ]
首先将其转换为最大堆，如下所示：
堆
此时堆的内部数组为：
[ 25, 13, 20, 8, 7, 17, 2, 5, 4 ]
现在开始对堆进行排序操作
- 将第一个元素索引0与n-1索引进行调换
[ 4, 13, 20, 8, 7, 17, 2, 5, 25 ]
* *
- 现在，新的根节点4将会小于其子节点，所以要使用shift down或
heapify过程，将最大堆固定为n-2。修复堆后，现在的根是数组中第二大的元素：
[20, 13, 17, 8, 7, 4, 2, 5 | 25]
- 将第一个元素与n-2索引处的元素进行调换
[5, 13, 17, 8, 7, 4, 2, 20 | 25]
* *
- 继续修复堆并使最大堆固定位n-3
[17, 13, 5, 8, 7, 4, 2 | 20, 25]
- 重复此过程，知道整个数组完成排序
...
堆排序与选择排序非常相似，选择排序会在数组其余部分反复查找最小值。对于堆排序来说，提取最小值或者最大值是最擅长的。
总结
在最佳，最差和平均情况下，堆排序的性能为O(N LogN)。因为我们直接修改数组，所以堆排序不需要额外的空间。但是堆排序并不稳定，不会保留相同元素的顺序。
