堆排序算法的基本操作是优秀

我们通常所说的堆是指二叉堆，二叉堆又称完全二叉树或者叫近似完全二叉树。二叉堆又分为最大堆和最小堆。

堆排序(heapsort)是指利用堆这种数据结构所设计的一种排序算法，它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。数组可以根据索引直接获取元素，时间复杂度为o（1），也就是常量，因此对于取值效率极高。

最大堆的特性如下：

父结点的键值总是大于或者等于任何一个子节点的键值 每个结点的左子树和右子树都是一个最大堆

最小堆的特性如下：

父结点的键值总是小于或者等于任何一个子节点的键值 每个结点的左子树和右子树都是一个最小堆

1.最大堆的算法思想是：

先将初始的r[0…n-1]建立成最大堆，此时是无序堆，而堆顶是最大元素

再将堆顶r[0]和无序区的最后一个记录r[n-1]交换，由此得到新的无序区r[0…n-2]和有序区r[n-1]，且满足r[0…n-2].keys ≤ r[n-1].key

由于交换后，前r[0…n-2]可能不满足最大堆的性质，因此再调整前r[0…n-2]为最大堆，直到只有r[0]最后一个元素才调整完成。

最大堆排序完成后，其实是升序序列，每次调整堆都是要得到最大的一个元素，然后与当前堆