堆排序

堆

堆排序是利用堆这种数据结构而设计的一种排序算法, 是一种选择排序, 它的最坏, 最好, 平均时间复杂度均为$O(n \log n)$.

堆是具有以下性质的完全二叉树: 每个结点的值都大于或等于其左右孩子结点的值, 称为大顶堆; 或者每个结点的值都小于或等于其左右孩子结点的值, 称为小顶堆.

同时, 堆是用数组实现的, 上图中大顶堆对应的数组为:

并不是完全顺序的.

最大堆/最小堆用公式表示为:

• 最大堆: $\text{arr}[i] \ge \text{arr}[2i+1], \quad \text{arr}[i] \ge \text{arr}[2i+2]$

• 最小堆: $\text{arr}[i] \le \text{arr}[2i+1], \quad \text{arr}[i] \le \text{arr}[2i+2]$

堆排序

堆排序(升序)的基本思想是: 将待排序序列构造成一个大顶堆, 整个序列的最大值就是堆顶的根节点. 将其与末尾元素进行交换, 此时末尾就为最大值. 然后剩余的$n-1$个元素重新构造成一个堆, 重复一次得到所有数字中第二大的值. 如此反复执行, 便能得到一个有序序列了.

完整的堆排序具体来说分为几个步骤.

构造初始堆

将给定无序序列构造成一个大顶堆(升序采用大顶堆, 降序采用小顶堆). 假设给定无序序列结构如下:

从最后一个非叶子节点开始(最后一个非叶子节点对应的索引为$\lfloor n / 2 \rfloor - 1$), 从左至右, 从下至上进行调整:

上面这步导致了子堆[4, 5, 6]结构混乱, 继续调整, 需要将4下沉:

此时, 我们就将一个无需序列构造成了一个大顶堆.

交换堆顶元素和末尾元素并重建堆

将堆顶元素与末尾元素进行交换, 使末尾元素最大. 最大的数被找到了, 而且也放在了数组的最后. 要在剩余的$n-1$个数继续找最大的数, 因此需要调整得到新的堆, 再将堆顶元素与末尾元素交换. 如此反复进行交换, 重建, 数组最后的部分就是排序好的大元素. 示例如下:

将堆顶元素9和末尾元素4进行交换:

重新调整结构, 使其继续满足堆定义:

再将堆顶元素8与末尾元素5进行交换, 得到第二大元素8:

后续过程, 继续进行调整, 交换, 如此反复进行, 最终使得整个序列有序:

时间复杂度

堆排序作为一种选择排序, 整体主要由构建初始堆和交换堆顶元素和末尾元素并重建堆两部分组成.

构建初始堆经推导复杂度为$O(n)$.

在交换并重建堆的过程中, 需交换$n-1$次, 而重建堆的过程中, 根据完全二叉树的性质, 对应的时间复杂度为$[\log(n-1), \log(n-2), \cdots, \log(1)]$逐步递减, 近似为$O(n \log n)$.

所以堆排序时间复杂度一般认为就是$O(n \log n)$.

参考资料

• 图解排序算法(三)之堆排序