堆排序（Heapsort）是指利用 二叉堆这种数据结构所设计的一种排序算法。堆排序的适用数据结构为数组。堆排序的本质是建立在堆上的选择排序。
- 首先建立大顶堆，然后将堆顶的元素取出，作为最大值，与数组尾部的元素交换，并维持残余堆的性质
- 之后将堆顶的元素取出，作为次大值，与数组倒数第二位元素交换，并维持残余堆的性质
- 以此类推，在第次操作后，整个数组就完成了排序
数组中下标为
i的节点，对应的父结点、左子结点和右子结点如下：时间复杂度
堆排序的最优时间复杂度、平均时间复杂度、最坏时间复杂度均为
代码实现