堆排序

堆排序简介

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

堆排序

  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比较小的场景

赫墨拉

我是一个喜爱大数据的小菜鸡,这里是我分享我的成长和经历的博客

发表评论

电子邮件地址不会被公开。