28 | 堆和堆排序：为什么说堆排序没有快速排序快？
王争
该思维导图由 AI 生成，仅供参考
我们今天讲另外一种特殊的树，“堆”（）。堆这种数据结构的应用场景非常多，最经典的莫过于堆排序了。堆排序是一种原地的、时间复杂度为 的排序算法。
前面我们学过快速排序，平均情况下，它的时间复杂度为 。尽管这两种排序算法的时间复杂度都是 ，甚至堆排序比快速排序的时间复杂度还要稳定，但是，在实际的软件开发中，快速排序的性能要比堆排序好，这是为什么呢？
现在，你可能还无法回答，甚至对问题本身还有点疑惑。没关系，带着这个问题，我们来学习今天的内容。等你学完之后，或许就能回答出来了。
如何理解“堆”？
前面我们提到，堆是一种特殊的树。我们现在就来看看，什么样的树才是堆。我罗列了两点要求，只要满足这两点，它就是一个堆。
堆是一个完全二叉树；
堆中每一个节点的值都必须大于等于（或小于等于）其子树中每个节点的值。
我分别解释一下这两点。
第一点，堆必须是一个完全二叉树。还记得我们之前讲的完全二叉树的定义吗？完全二叉树要求，除了最后一层，其他层的节点个数都是满的，最后一层的节点都靠左排列。
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线笔记
复制
AI
- 深入了解
- 翻译
- 解释
- 总结
堆排序是一种原地的、时间复杂度为$O(n\log n)$的排序算法，但在实际软件开发中，快速排序的性能要比堆排序好。文章介绍了堆的特点和实现方法，以及基于堆实现的排序算法——堆排序。堆是一种特殊的树，满足完全二叉树和每个节点的值大于等于（或小于等于）其子树中每个节点的值。堆排序包括建堆和排序两个步骤，时间复杂度稳定为$O(n\log n)$，并且是原地排序算法。文章详细介绍了堆的存储方式、插入和删除操作，以及堆排序的实现过程。通过对堆排序的介绍，读者可以快速了解堆排序的特点和实现方法。 堆排序的建堆过程的时间复杂度是$O(n)$，而排序过程的时间复杂度是$O(n\log n)$，整体的时间复杂度是$O(n\log n)$。堆排序是原地排序算法，但不是稳定的排序算法，因为在排序的过程中存在数据交换操作，可能改变值相同数据的原始相对顺序。堆排序的性能不如快速排序的主要原因在于数据访问方式不友好，以及在排序过程中数据交换次数多于快速排序。 总的来说，本文介绍了堆排序的原理、实现方法以及性能特点，帮助读者快速了解堆排序的特点和适用场景。
仅可试看部分内容，如需阅读全部内容，请付费购买文章所属专栏
《数据结构与算法之美》，新⼈⾸单¥68
《数据结构与算法之美》，新⼈⾸单¥68
立即购买
© 版权归极客邦科技所有，未经许可不得传播售卖。 页面已增加防盗追踪，如有侵权极客邦将依法追究其法律责任。
登录 后留言
全部留言(248)
- 最新
- 精选
WhoAmWe应用: 1.topK 2.流里面的中值 3.流里面的中位数作者回复: 👍
2018-11-266123
insist这种数据结构堆和java内存模型中的堆内存有什么关系呢？作者回复: 完全没关系的。
2018-11-26369
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-26834
鲍勃linux内核内存中的堆和这个有关系吗？作者回复: 没关系 完全是两个东西
2018-11-30219
."对堆顶节点进行堆化，会依次访问数组下标是 1，2，4，8"。这里图画错了吧，数组下标2 (20)和数组下标3(21)的位置应该是弄反了。如果按原图对堆顶元素堆化的话顺序应该是1,3,6不应该是1,2,4,8作者回复: 嗯嗯 多谢指正
2018-12-149
博予liutxer堆排序和快速排序相比实际开发中不如后者性能好，那堆排序在哪些场景比较有优势呢？作者回复: 时间复杂度比较稳定 有些排序函数会使用这种排序算法
2018-12-098
小方本节的堆排序代码sort()方法，while循环体里，交换完堆尾和a[1]后，不应该是调用buildHeap()方法吗？文中的调用的是heapify(a, k, 1)，这个方法只是针对某个特定节点啊，没有操作整个堆。 望小争哥看一眼。作者回复: 因为交换完之后，只有那一个结点不符合堆的特性，需要处理，其他结点都满足堆的特性，所以只需要对这个结点进行heapify即可，不需要重新buildHeap
2019-11-095
落叶飞逝的恋建堆的过程采用方法1与方法2，在实际应用有区别吗？作者回复: 第二种方法效率更高些。
2019-03-155
fumeck.com🍋🌴summer sk...我们将下标从 n/2 到 1的节点，依次进行从上到下的堆化操作 不是由下往上吗老师，最后一个才轮到根节点阿作者回复: 哈哈 弄混淆了 堆化是有两种方式：从上到下和从下到上，前面讲到了。我这里说的从下到上，是指的堆化操作本身。
2018-11-2625
Jalyn因为叶子节点往下堆化只能自己跟自己比较，所以我们直接从第一个非叶子节点开始，依次堆化就行了。 这边应该是最后一个非叶子节点吧？作者回复: 嗯嗯 是的
2018-12-123
收起评论
