概述

堆排序是一种利用堆数据结构进行排序的排序算法。其先将数组转换为大顶堆，再进行相应处理拿出最大值。其与选择排序的思想大同小异，但是时间复杂度和空间复杂度就要低很多。
时间复杂度：$O(N\ast lo{g}_2^N)$
空间复杂度：$O(1)$
我们将先简要介绍一下堆这种数据结构，为之后构建堆排序奠定基础。

堆

堆结构的本质就是完全二叉树。
有两种堆，大顶堆和小顶堆。前者的父节点的都大于等于其子节点，后者的父节点均小于等于其子节点。所以，我们不难发现，大顶堆的根节点永远是各结点的最大值，小顶堆的根节点永远是各结点中的最小值，于是根据这个性质，我们就有了排序的思路。
总结，大根（小根）堆的条件为：
1. 完全二叉树；
2. 任意父节点（非叶子节点）都大于其子节点；
时间复杂度：堆每一次调整（加入和弹出）操作的时间复杂度为 $O(logN)$。

代码实现

模板

838-堆排序

加强堆