数据结构与算法之美
王争
前Google工程师
立即订阅
71638 人已学习
课程目录
已完结 75 讲
0/4登录后,你可以任选4讲全文学习。
开篇词 (1讲)
开篇词 | 从今天起,跨过“数据结构与算法”这道坎
免费
入门篇 (4讲)
01 | 为什么要学习数据结构和算法?
02 | 如何抓住重点,系统高效地学习数据结构与算法?
03 | 复杂度分析(上):如何分析、统计算法的执行效率和资源消耗?
04 | 复杂度分析(下):浅析最好、最坏、平均、均摊时间复杂度
基础篇 (38讲)
05 | 数组:为什么很多编程语言中数组都从0开始编号?
06 | 链表(上):如何实现LRU缓存淘汰算法?
07 | 链表(下):如何轻松写出正确的链表代码?
08 | 栈:如何实现浏览器的前进和后退功能?
09 | 队列:队列在线程池等有限资源池中的应用
10 | 递归:如何用三行代码找到“最终推荐人”?
11 | 排序(上):为什么插入排序比冒泡排序更受欢迎?
12 | 排序(下):如何用快排思想在O(n)内查找第K大元素?
13 | 线性排序:如何根据年龄给100万用户数据排序?
14 | 排序优化:如何实现一个通用的、高性能的排序函数?
15 | 二分查找(上):如何用最省内存的方式实现快速查找功能?
16 | 二分查找(下):如何快速定位IP对应的省份地址?
17 | 跳表:为什么Redis一定要用跳表来实现有序集合?
18 | 散列表(上):Word文档中的单词拼写检查功能是如何实现的?
19 | 散列表(中):如何打造一个工业级水平的散列表?
20 | 散列表(下):为什么散列表和链表经常会一起使用?
21 | 哈希算法(上):如何防止数据库中的用户信息被脱库?
22 | 哈希算法(下):哈希算法在分布式系统中有哪些应用?
23 | 二叉树基础(上):什么样的二叉树适合用数组来存储?
24 | 二叉树基础(下):有了如此高效的散列表,为什么还需要二叉树?
25 | 红黑树(上):为什么工程中都用红黑树这种二叉树?
26 | 红黑树(下):掌握这些技巧,你也可以实现一个红黑树
27 | 递归树:如何借助树来求解递归算法的时间复杂度?
28 | 堆和堆排序:为什么说堆排序没有快速排序快?
29 | 堆的应用:如何快速获取到Top 10最热门的搜索关键词?
30 | 图的表示:如何存储微博、微信等社交网络中的好友关系?
31 | 深度和广度优先搜索:如何找出社交网络中的三度好友关系?
32 | 字符串匹配基础(上):如何借助哈希算法实现高效字符串匹配?
33 | 字符串匹配基础(中):如何实现文本编辑器中的查找功能?
34 | 字符串匹配基础(下):如何借助BM算法轻松理解KMP算法?
35 | Trie树:如何实现搜索引擎的搜索关键词提示功能?
36 | AC自动机:如何用多模式串匹配实现敏感词过滤功能?
37 | 贪心算法:如何用贪心算法实现Huffman压缩编码?
38 | 分治算法:谈一谈大规模计算框架MapReduce中的分治思想
39 | 回溯算法:从电影《蝴蝶效应》中学习回溯算法的核心思想
40 | 初识动态规划:如何巧妙解决“双十一”购物时的凑单问题?
41 | 动态规划理论:一篇文章带你彻底搞懂最优子结构、无后效性和重复子问题
42 | 动态规划实战:如何实现搜索引擎中的拼写纠错功能?
高级篇 (9讲)
43 | 拓扑排序:如何确定代码源文件的编译依赖关系?
44 | 最短路径:地图软件是如何计算出最优出行路径的?
45 | 位图:如何实现网页爬虫中的URL去重功能?
46 | 概率统计:如何利用朴素贝叶斯算法过滤垃圾短信?
47 | 向量空间:如何实现一个简单的音乐推荐系统?
48 | B+树:MySQL数据库索引是如何实现的?
49 | 搜索:如何用A*搜索算法实现游戏中的寻路功能?
50 | 索引:如何在海量数据中快速查找某个数据?
51 | 并行算法:如何利用并行处理提高算法的执行效率?
实战篇 (5讲)
52 | 算法实战(一):剖析Redis常用数据类型对应的数据结构
53 | 算法实战(二):剖析搜索引擎背后的经典数据结构和算法
54 | 算法实战(三):剖析高性能队列Disruptor背后的数据结构和算法
55 | 算法实战(四):剖析微服务接口鉴权限流背后的数据结构和算法
56 | 算法实战(五):如何用学过的数据结构和算法实现一个短网址系统?
加餐:不定期福利 (6讲)
不定期福利第一期 | 数据结构与算法学习书单
不定期福利第二期 | 王争:羁绊前行的,不是肆虐的狂风,而是内心的迷茫
不定期福利第三期 | 测一测你的算法阶段学习成果
不定期福利第四期 | 刘超:我是怎么学习《数据结构与算法之美》的?
总结课 | 在实际开发中,如何权衡选择使用哪种数据结构和算法?
《数据结构与算法之美》学习指导手册
加餐:春节7天练 (7讲)
春节7天练 | Day 1:数组和链表
春节7天练 | Day 2:栈、队列和递归
春节7天练 | Day 3:排序和二分查找
春节7天练 | Day 4:散列表和字符串
春节7天练 | Day 5:二叉树和堆
春节7天练 | Day 6:图
春节7天练 | Day 7:贪心、分治、回溯和动态规划
加餐:用户学习故事 (2讲)
用户故事 | Jerry银银:这一年我的脑海里只有算法
用户故事 | zixuan:站在思维的高处,才有足够的视野和能力欣赏“美”
结束语 (3讲)
结束语 | 送君千里,终须一别
第2季回归 | 这一次,我们一起拿下设计模式!
打卡召集令 | 60 天攻克数据结构与算法
免费
数据结构与算法之美
登录|注册

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

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

如何理解“堆”?

前面我们提到,堆是一种特殊的树。我们现在就来看看,什么样的树才是堆。我罗列了两点要求,只要满足这两点,它就是一个堆。
堆是一个完全二叉树;
堆中每一个节点的值都必须大于等于(或小于等于)其子树中每个节点的值。
我分别解释一下这两点。
第一点,堆必须是一个完全二叉树。还记得我们之前讲的完全二叉树的定义吗?完全二叉树要求,除了最后一层,其他层的节点个数都是满的,最后一层的节点都靠左排列。
取消
完成
0/1000字
划线
笔记
复制
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
该试读文章来自付费专栏《数据结构与算法之美》,如需阅读全部文章,
请订阅文章所属专栏。
立即订阅
登录 后留言

精选留言(131)

  • Jerry银银
    ## 第一题:

    使用数组存储表示完全二叉树时,从数组下标为1开始存储数据,数组下标为i的节点,左子节点为2i, 右子节点为2i + 1. 这个结论很重要(可以用数学归纳法证明),将此结论记为『原理1』,以下证明会用到这个原理。

    为什么,对于完全二叉树来说,下标从n/2 + 1 到 n的节点都是叶子节点? 使用反证法证明即可:

    如果下标为n/2 + 1的节点不是叶子节点,即它存在子节点,按照『原理1』,它的左子节点为:2(n/2 + 1) = n + 2,大家明显可以看出,这个数字已经大于n + 1,超出了实现完全二叉树所用数组的大小(数组下标从1开始记录数据,对于n个节点来说,数组大小是n + 1),左子节点都已经超出了数组容量,更何况右子节点。以此类推,很容易得出:下标大于n/2 + 1的节点肯定都是也叶子节点了,故而得出结论:对于完全二叉树来说,下标从n/2 + 1 到 n的节点都是叶子节点

    备注下:用数组存储表示完全二叉树时,也可以从下标为0开始,只是这样做的话,计算左子节点时,会多一次加法运算

    --------------------------------------------------------
    ## 第二题:

    堆的应用除了堆排以外,还有如下一些应用:
    1. 从大数量级数据中筛选出top n 条数据; 比如:从几十亿条订单日志中筛选出金额靠前的1000条数据
    2. 在一些场景中,会根据不同优先级来处理网络请求,此时也可以用到优先队列(用堆实现的数据结构);比如:网络框架Volley就用了Java中PriorityBlockingQueue,当然它是线程安全的
    3. 可以用堆来实现多路归并,从而实现有序,leetcode上也有相关的一题:Merge K Sorted Lists

    暂时只能想到以上三种常见的应用场景,其它的,希望老师补充!
    2018-11-26
    5
    228
  • Jessie
    强烈建议,在进入课程的左侧,做一个目录,这样就不用每次都从最新的滑到最下面了。例如:目前是学到了第35课,已进入课堂,就是35课,假如我想看第一课,就得使劲滑。如果学到100课,那得滑老半天……所以强烈建议给左侧添加一个目录。可以连接到每一节课。!!!
    2018-12-13
    3
    123
  • WhoAmWe
    应用:
    1.topK
    2.流里面的中值
    3.流里面的中位数

    作者回复: 👍

    2018-11-26
    2
    50
  • 大冯宇宙
    不知道有没有人很容易看懂原理思路,就是不愿意看代码
    2018-11-27
    4
    45
  • 无心拾贝
    这TM估计是我唯一看的懂的数据结构与算法吧。 谢谢老师!
    2018-11-26
    29
  • 猫头鹰爱拿铁
    思考题1:堆是完全二叉树,求最后的非叶子节点即是求最大的叶子节点的父节点。最大的叶子节点下标为n,他的父节点为n/2,这是最后一个非叶子节点,所以n/2+1到n都是叶子节点。
    思考题2:堆排序的应用-topk问题,例如求数据频率最高的k个数,建立k个数的最小顶堆,然后剩余数据和堆顶比较,如果比堆顶大则替换堆顶并重新调整最小顶堆。
    2018-11-26
    2
    24
  • insist
    这种数据结构堆和java内存模型中的堆内存有什么关系呢?

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

    2018-11-26
    22
  • Smallfly
    堆应该可以用于实现优先级队列。
    2018-11-26
    13
  • 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
    4
    12
  • 鲍勃
    linux内核内存中的堆和这个有关系吗?

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

    2018-11-30
    7
  • Brandon
    排序队------时间复杂度
    堆满足两条:1、完全二叉树(可以很方便的使用数组存储),2、父节点大于或小于子节点-----
    插入元素-先放入队尾,再进行堆化(heapify)
    删除元素-从最后取一个元素放到删除元素位置,从上往下调整

    快排比堆排性能好的原因有二:1、堆排序数据访问的方式有没有快速排序友好;
    2、对于同样的数据,在排序的过程中堆排序算法的交换次数多于快速排序
    2018-12-14
    5
  • 李建轰
    老师你好~
    heapify方法好像有点问题?
    假如第一个非叶子节点是5,左叶子节点是7,右叶子节点是6
    然后入heapify方法的这段代码
    ```
    while (true) {
        int maxPos = i;
        if (i*2 <= n && a[i] < a[i*2]) maxPos = i*2;
        if (i*2+1 <= n && a[i] < a[i*2+1]) maxPos = i*2+1
        if (maxPos == i) break;
        swap(a, i, maxPos);
        i = maxPos;
    }
    ```
    就会变成第一个非叶子节点是6,左叶子节点是7,右叶子节点是5,因为swap只会执行一次。
    我觉得swap方法在前面两个if里面都得有,并且第二个if必须用if,不能用else if。
    斗胆提问,请老师答疑~
    2018-11-30
    1
    5
  • .
    "对堆顶节点进行堆化,会依次访问数组下标是 1,2,4,8"。这里图画错了吧,数组下标2 (20)和数组下标3(21)的位置应该是弄反了。如果按原图对堆顶元素堆化的话顺序应该是1,3,6不应该是1,2,4,8

    作者回复: 嗯嗯 多谢指正

    2018-12-14
    4
  • 若星
    删除堆顶元素的代码第二行return -1。。
    2018-12-12
    4
  • yaya
    最后一个结点的父节点是n/2.这是最后一个非叶子结点所以,叶子结点是n/2+1到n。
    优先队列的实现用的就是堆
    2018-11-26
    4
  • qinggeouye
    重点:父节点和它的左右子节点比较大小关系,并交换。
    对于某个节点:
    从上往下堆化,时间复杂度和高度成正比
    从下往上堆化,时间复杂度和深度成正比
    2018-12-23
    3
  • 博予liutxer
    堆排序和快速排序相比实际开发中不如后者性能好,那堆排序在哪些场景比较有优势呢?

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

    2018-12-09
    3
  • Vinegar.
    Java 中的 PriorityQueue 就是基于堆的数据结构的
    2018-11-26
    3
  • 小二黑
    老师,请问堆化自上而下,那段代码,节点和子节点比较大小,是用if判断的吗

    作者回复: if判断是什么意思呢

    2019-03-27
    2
  • 『LHCY』
    刚才面试遇到了这道题,不过没想起来
    2019-02-18
    2
收起评论
99+
返回
顶部