春节7天练Day3:排序和二分查找.pdf
《春节7天练Day3:排序和二分查找.pdf》由会员分享,可在线阅读,更多相关《春节7天练Day3:排序和二分查找.pdf(14页珍藏版)》请在文库网上搜索。
1、28|堆和堆排序:为什么说堆排序没有快速排序快? file:/F/temp/geektime/数据结构与算法之美/28堆和堆排序:为什么说堆排序没有快速排序快?.html2019/1/15 15:36:02 28|堆和堆排序:为什么说堆排序没有快速排序快? 我们今天讲另外一种特殊的树,“堆”($Heap$)。堆这种数据结构的应用场景非常多,最经典的莫过于堆排序了。堆排序是一种原地的、时间复杂度为$O(nlog n)$的排序算法。 前面我们学过快速排序,平均情况下,它的时间复杂度为$O(nlog n)$。尽管这两种排序算法的时间复杂度都是$O(nlog n)$,甚至堆排序比快速排序的时间复杂度
2、还要稳定,但是,在实际的软件开发中,快速排序的性能要比堆排序好,这是为什么呢? 现在,你可能还无法回答,甚至对问题本身还有点疑惑。没关系,带着这个问题,我们来学习今天的内容。等你学完之后,或许就能回答出来了。 如何理解“堆”? 前面我们提到,堆是一种特殊的树。我们现在就来看看,什么样的树才是堆。我罗列了两点要求,只要满足这两点,它就是一个堆。 堆是一个完全二叉树; 堆中每一个节点的值都必须大于等于(或小于等于)其子树中每个节点的值。 我分别解释一下这两点。 第一点,堆必须是一个完全二叉树。还记得我们之前讲的完全二叉树的定义吗?完全二叉树要求,除了最后一层,其他层的节点个数都是满的,最后一层的节
3、点 都靠左排列。 第二点,堆中的每个节点的值必须大于等于(或者小于等于)其子树中每个节点的值。实际上,我们还可以换一种说法,堆中每个节点的值都大于等于(或者小 于等于)其左右子节点的值。这两种表述是等价的。 对于每个节点的值都大于等于子树中每个节点值的堆,我们叫作“大顶堆”。对于每个节点的值都小于等于子树中每个节点值的堆,我们叫作“小顶堆”。 定义解释清楚了,你来看看,下面这几个二叉树是不是堆? 28|堆和堆排序:为什么说堆排序没有快速排序快? file:/F/temp/geektime/数据结构与算法之美/28堆和堆排序:为什么说堆排序没有快速排序快?.html2019/1/15 15:36
4、:02 其中第$1$个和第$2$个是大顶堆,第$3$个是小顶堆,第$4$个不是堆。除此之外,从图中还可以看出来,对于同一组数据,我们可以构建多种不同形态的堆。 28|堆和堆排序:为什么说堆排序没有快速排序快? file:/F/temp/geektime/数据结构与算法之美/28堆和堆排序:为什么说堆排序没有快速排序快?.html2019/1/15 15:36:02 如何实现一个堆? 要实现一个堆,我们先要知道,堆都支持哪些操作以及如何存储一个堆。 我之前讲过,完全二叉树比较适合用数组来存储。用数组来存储完全二叉树是非常节省存储空间的。因为我们不需要存储左右子节点的指针,单纯地通过数组的 下标,
5、就可以找到一个节点的左右子节点和父节点。 我画了一个用数组存储堆的例子,你可以先看下。 从图中我们可以看到,数组中下标为$i$的节点的左子节点,就是下标为$i*2$的节点,右子节点就是下标为$i*2+1$的节点,父节点就是下标为$fraci2$的节 点。 知道了如何存储一个堆,那我们再来看看,堆上的操作有哪些呢?我罗列了几个非常核心的操作,分别是往堆中插入一个元素和删除堆顶元素。(如果没有特殊 28|堆和堆排序:为什么说堆排序没有快速排序快? file:/F/temp/geektime/数据结构与算法之美/28堆和堆排序:为什么说堆排序没有快速排序快?.html2019/1/15 15:36:
6、02 说明,我下面都是拿大顶堆来讲解)。 1.往堆中插入一个元素 往堆中插入一个元素后,我们需要继续满足堆的两个特性。 如果我们把新插入的元素放到堆的最后,你可以看我画的这个图,是不是不符合堆的特性了?于是,我们就需要进行调整,让其重新满足堆的特性,这个过程我 们起了一个名字,就叫作堆化(heapify)。 堆化实际上有两种,从下往上和从上往下。这里我先讲从下往上的堆化方法。 28|堆和堆排序:为什么说堆排序没有快速排序快? file:/F/temp/geektime/数据结构与算法之美/28堆和堆排序:为什么说堆排序没有快速排序快?.html2019/1/15 15:36:02 堆化非常简单
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 春节 Day3 排序 二分 查找