堆排序简介

堆

– 完全二叉树
– 父节点的值 >= 子节点（大根堆）/ 父节点的值 <= 子节点（小根堆）

堆排序

1. 构造一个大根堆/小根堆
2. 取出堆顶元素（最大值/最小值）
3. 将剩下的元素再构建一个大根堆/小根堆，取堆顶元素（将剩下的元素取最大值/最小值）
4. 重复以上操作，直到取完堆中元素
5. 获得一个有序的序列
   – 实质：利用完全二叉树中父节点与子节点之间的内在关系来排序

如何实现堆排序

1. 如何构建堆：如何由无序序列构建成堆？
2. 如何调整堆：如何在输出堆顶元素后，调整剩余元素？
   – 构建堆
   – 堆实质上是一个线性表，可以使用顺序存储（数组）
   1. 从完全二叉树的最后一个非叶子节点（序号 i = N / 2 , i 取整 ）开始，即由N个元素组成的无序序列，从第 N / 2 个元素开始调整
   2. 再以 N / 2 – 1 的节点为根的二叉树开始调整
   3. 再以 N / 2 – 2 的节点为根的二叉树开始调整
   4. 再以 N / 2 – 3 的节点为根的二叉树开始调整
      – 调整堆
      – 小根堆调整
   5. 取出堆顶元素后，以堆中$\color{red}{最后一个元素代替堆顶元素}$
   6. 将根节点值与左右子树的根节点值进行比较，并与其中$\color{red}{较小者}$进行交换
   7. 重复上述操作，直至叶子节点，将得到新的堆，这个从堆顶到叶子节点的操作，称$\color{red}{筛选/调整}$
      – 大根堆调整
   8. 取出堆顶元素后，以堆中$\color{red}{最后一个元素代替堆顶元素}$
   9. 将根节点值与左右子树的根节点值进行比较，并与其中$\color{red}{较大者}$进行交换
   10. 重复上述操作，直至叶子节点，将得到新的堆

算法性能分析

– 初始堆所需时间：O(n)

– 排序阶段：（不包含堆初始化）
– 重新构建堆所需时间，不超过O($\log_2 N$)
– n -1 次循环所需时间，不超过O(n $\log_2 N$)
– 时间复杂度：O(n $\log_2 N$ )
– 空间复杂度：O(1)
– 优点：堆排序在最坏情况下，无论是正序还是倒序，时间复杂度也为O(n $\log_2 N$ )
– 缺点：不稳定的排序，不适用于N比较小的场景