数据结构与算法之美
王争
前 Google 工程师
283752 人已学习
新⼈⾸单¥68
登录后,你可以任选4讲全文学习
课程目录
已完结/共 81 讲
基础篇 (38讲)
数据结构与算法之美
15
15
1.0x
00:00/00:00
登录|注册

28 | 堆和堆排序:为什么说堆排序没有快速排序快?

堆排序:建堆过程打乱原有顺序
快速排序:不会超过逆序度
堆排序:跳着访问
快速排序:顺序访问
数据交换次数
数据访问方式
不稳定排序算法
时间复杂度:O(nlogn)
从上往下堆化
交换堆顶和最后一个元素
时间复杂度:O(n)
从后往前堆化
原地建堆
小顶堆
大顶堆
完全二叉树
在实际开发中,快速排序性能优于堆排序
堆排序不是稳定的排序算法
堆排序的建堆过程时间复杂度为O(n),排序过程时间复杂度为O(nlogn)
堆排序是原地排序算法,时间复杂度为O(nlogn)
性能比较
排序
建堆
总结
堆排序

该思维导图由 AI 生成,仅供参考

我们今天讲另外一种特殊的树,“堆”()。堆这种数据结构的应用场景非常多,最经典的莫过于堆排序了。堆排序是一种原地的、时间复杂度为 的排序算法。
前面我们学过快速排序,平均情况下,它的时间复杂度为 。尽管这两种排序算法的时间复杂度都是 甚至堆排序比快速排序的时间复杂度还要稳定,但是,在实际的软件开发中,快速排序的性能要比堆排序好,这是为什么呢?
现在,你可能还无法回答,甚至对问题本身还有点疑惑。没关系,带着这个问题,我们来学习今天的内容。等你学完之后,或许就能回答出来了。

如何理解“堆”?

前面我们提到,堆是一种特殊的树。我们现在就来看看,什么样的树才是堆。我罗列了两点要求,只要满足这两点,它就是一个堆。
堆是一个完全二叉树;
堆中每一个节点的值都必须大于等于(或小于等于)其子树中每个节点的值。
我分别解释一下这两点。
第一点,堆必须是一个完全二叉树。还记得我们之前讲的完全二叉树的定义吗?完全二叉树要求,除了最后一层,其他层的节点个数都是满的,最后一层的节点都靠左排列。
确认放弃笔记?
放弃后所记笔记将不保留。
新功能上线,你的历史笔记已初始化为私密笔记,是否一键批量公开?
批量公开的笔记不会为你同步至部落
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线
笔记
复制
AI
  • 深入了解
  • 翻译
    • 英语
    • 中文简体
    • 中文繁体
    • 法语
    • 德语
    • 日语
    • 韩语
    • 俄语
    • 西班牙语
    • 阿拉伯语
  • 解释
  • 总结

堆排序是一种原地的、时间复杂度为$O(n\log n)$的排序算法,但在实际软件开发中,快速排序的性能要比堆排序好。文章介绍了堆的特点和实现方法,以及基于堆实现的排序算法——堆排序。堆是一种特殊的树,满足完全二叉树和每个节点的值大于等于(或小于等于)其子树中每个节点的值。堆排序包括建堆和排序两个步骤,时间复杂度稳定为$O(n\log n)$,并且是原地排序算法。文章详细介绍了堆的存储方式、插入和删除操作,以及堆排序的实现过程。通过对堆排序的介绍,读者可以快速了解堆排序的特点和实现方法。 堆排序的建堆过程的时间复杂度是$O(n)$,而排序过程的时间复杂度是$O(n\log n)$,整体的时间复杂度是$O(n\log n)$。堆排序是原地排序算法,但不是稳定的排序算法,因为在排序的过程中存在数据交换操作,可能改变值相同数据的原始相对顺序。堆排序的性能不如快速排序的主要原因在于数据访问方式不友好,以及在排序过程中数据交换次数多于快速排序。 总的来说,本文介绍了堆排序的原理、实现方法以及性能特点,帮助读者快速了解堆排序的特点和适用场景。

仅可试看部分内容,如需阅读全部内容,请付费购买文章所属专栏
《数据结构与算法之美》
新⼈⾸单¥68
立即购买
登录 后留言

全部留言(248)

  • 最新
  • 精选
  • WhoAmWe
    应用: 1.topK 2.流里面的中值 3.流里面的中位数

    作者回复: 👍

    2018-11-26
    6
    123
  • insist
    这种数据结构堆和java内存模型中的堆内存有什么关系呢?

    作者回复: 完全没关系的。

    2018-11-26
    3
    69
  • 1024
    思考题1证明 结论:对于完全二叉树来说,下标从(n/2)+1到n都是叶子节点 证明: 假设堆有n个节点 假设满二叉树有h层 则满二叉树的总节点数 2^0+2^1...+2^(h-2)+2^(h-1)=(2^h)-1> n n为h层完全二叉树节点数 堆为完全二叉树,相同高度,完全二叉树总结点数小于满二叉树节点数,即n<(2^h)-1, 即(2^h)>n+1 -----① 完全二叉树1到h-1层节点的数量总和: 2^0+2^1...+2^(h-2)=(2^(h-1))-1=(2^h)/2 -1 -----② 如果数组的第0位也存储数据,由②可知,完全二叉树的第h层开始的节点的下标为i=(2^h)/2 -1,由①,i>((n+1)/2)-1=(n/2)+1 结论1:如果数组的第0位也存储数据,完全二叉树的节点下标至少开始于(n/2)+1 如果数组的第0位不存储数据,则由②可知,完全二叉树的第h层开始的节点的下标为j=(2^h)/2,由①,j>(n+1)/2=(n/2)+2 结论2:如果数组的第0位不存储数据,完全二叉树的节点下标至少开始于(n/2)+2 综上,堆(完全二叉树)的叶子节点的下标范围从(n/2)+1到n-1或从(n/2)+2到n,也即堆的叶子节点下标从(n/2)+1到n 欢迎指正 --不为别的,就为成为更合格的自己

    作者回复: 👍

    2019-02-26
    8
    34
  • 鲍勃
    linux内核内存中的堆和这个有关系吗?

    作者回复: 没关系 完全是两个东西

    2018-11-30
    2
    19
  • .
    "对堆顶节点进行堆化,会依次访问数组下标是 1,2,4,8"。这里图画错了吧,数组下标2 (20)和数组下标3(21)的位置应该是弄反了。如果按原图对堆顶元素堆化的话顺序应该是1,3,6不应该是1,2,4,8

    作者回复: 嗯嗯 多谢指正

    2018-12-14
    9
  • 博予liutxer
    堆排序和快速排序相比实际开发中不如后者性能好,那堆排序在哪些场景比较有优势呢?

    作者回复: 时间复杂度比较稳定 有些排序函数会使用这种排序算法

    2018-12-09
    8
  • 小方
    本节的堆排序代码sort()方法,while循环体里,交换完堆尾和a[1]后,不应该是调用buildHeap()方法吗?文中的调用的是heapify(a, k, 1),这个方法只是针对某个特定节点啊,没有操作整个堆。 望小争哥看一眼。

    作者回复: 因为交换完之后,只有那一个结点不符合堆的特性,需要处理,其他结点都满足堆的特性,所以只需要对这个结点进行heapify即可,不需要重新buildHeap

    2019-11-09
    5
  • 落叶飞逝的恋
    建堆的过程采用方法1与方法2,在实际应用有区别吗?

    作者回复: 第二种方法效率更高些。

    2019-03-15
    5
  • fumeck.com🍋🌴summer sk...
    我们将下标从 n/2 到 1的节点,依次进行从上到下的堆化操作 不是由下往上吗老师,最后一个才轮到根节点阿

    作者回复: 哈哈 弄混淆了 堆化是有两种方式:从上到下和从下到上,前面讲到了。我这里说的从下到上,是指的堆化操作本身。

    2018-11-26
    2
    5
  • Jalyn
    因为叶子节点往下堆化只能自己跟自己比较,所以我们直接从第一个非叶子节点开始,依次堆化就行了。 这边应该是最后一个非叶子节点吧?

    作者回复: 嗯嗯 是的

    2018-12-12
    3
收起评论
显示
设置
留言
99+
收藏
沉浸
阅读
分享
手机端
快捷键
回顶部