保定免费建站服务,高端定制开发网站,进入微信公众号首页,二维码插件wordpress目录 前言如何理解“堆”#xff1f;如何实现一个堆#xff1f;1. 往堆中插入一个元素2. 删除堆顶元素 如何基于堆实现排序#xff1f;1. 建堆2. 排序 解答开篇内容小结 前言 本节课程思维导图#xff1a; 我们今天讲另外一种特殊的树#xff0c;“堆”#xff08;Heap如何实现一个堆1. 往堆中插入一个元素2. 删除堆顶元素 如何基于堆实现排序1. 建堆2. 排序 解答开篇内容小结 前言 本节课程思维导图 我们今天讲另外一种特殊的树“堆”Heap。堆这种数据结构的应用场景非常多最经典的莫过于堆排序了。堆排序是一种原地的、时间复杂度为 O(nlogn) 的排序算法。 快速排序和堆排序这两种排序算法的时间复杂度都是 O(nlogn)甚至堆排序比快速排序的时间复杂度还要稳定但是在实际的软件开发中快速排序的性能要比堆排序好这是为什么呢
如何理解“堆”
我们现在就来看看什么样的树才是堆。我罗列了两点要求只要满足这两点它就是一个堆。
堆是一个完全二叉树堆中每一个节点的值都必须大于等于或小于等于其子树中每个节点的值。
第一点堆必须是一个完全二叉树。完全二叉树要求除了最后一层其他层的节点个数都是满的最后一层的节点都靠左排列。 第二点堆中的每个节点的值必须大于等于或者小于等于其子树中每个节点的值。实际上我们还可以换一种说法堆中每个节点的值都大于等于或者小于等于其左右子节点的值。这两种表述是等价的。 对于每个节点的值都大于等于子树中每个节点值的堆我们叫做“大顶堆”。对于每个节点的值都小于等于子树中每个节点值的堆我们叫做“小顶堆”。
如何实现一个堆
要实现一个堆我们先要知道堆都支持哪些操作以及如何存储一个堆。 完全二叉树比较适合用数组来存储。用数组来存储完全二叉树是非常节省存储空间的。 假设堆中的数据是从数组下标为 1 的位置开始存储我们来看一个用数组存储堆的例子。 从图中我们可以看到数组中下标为 i 的节点的左子节点就是下标为 i∗2 的节点右子节点就是下标为 i∗21 的节点父节点就是下标为 i∗1/2的节点。
知道了如何存储一个堆那我们再来看看堆上的操作有哪些呢我罗列了几个非常核心的操作分别是往堆中插入一个元素和删除堆顶元素。
1. 往堆中插入一个元素
往堆中插入一个元素后我们需要继续满足堆的两个特性。如果我们把新插入的元素放到堆的最后不符合堆的特性我们就需要进行调整让其重新满足堆的特性这个过程我们起了一个名字就叫做堆化heapify。 堆化实际上有两种从下往上和从上往下。这里我先讲从下往上的堆化方法。 堆化非常简单就是顺着节点所在的路径向上或者向下对比然后交换。我们可以让新插入的节点与父节点对比大小。如果不满足子节点小于等于父节点的大小关系我们就互换两个节点。一直重复这个过程直到父子节点之间满足刚说的那种大小关系。
2. 删除堆顶元素
从堆的定义的第二条中任何节点的值都大于等于或小于等于子树节点的值我们可以发现堆顶元素存储的就是堆中数据的最大值或者最小值。 假设我们构造的是大顶堆堆顶元素就是最大的元素。我们把最后一个节点放到堆顶然后利用同样的父子节点对比方法。对于不满足父子节点大小关系的互换两个节点并且重复进行这个过程直到父子节点之间满足大小关系为止。这就是从上往下的堆化方法。 我们知道一个包含 n 个节点的完全二叉树树的高度不会超过 log2n。堆化的过程是顺着节点所在路径比较交换的所以堆化的时间复杂度跟树的高度成正比也就是 O(logn)。插入数据和删除堆顶元素的主要逻辑就是堆化所以往堆中插入一个元素和删除堆顶元素的时间复杂度都是 O(logn)。
如何基于堆实现排序
我们可以把堆排序的过程大致分解成两个大的步骤建堆和排序。
1. 建堆
我们首先将数组原地建成一个堆。所谓“原地”就是不借助另一个数组就在原数组上操作。 建堆过程的路是从后往前处理数组并且每个数据都是从上往下堆化。因为叶子节点往下堆化只能自己跟自己比较所以我们直接从最后一个非叶子节点开始依次堆化就行了。 现在我们来看建堆操作的时间复杂度是多少呢因为叶子节点不需要堆化所以需要堆化的节点从倒数第二层开始。每个节点堆化的过程中需要比较和交换的节点个数跟这个节点的高度 k 成正比。 我们将每个非叶子节点的高度求和就是下面这个公式 最终的结果就是下面图中画的这个样子。 因为 hlog2n代入公式 S就能得到 SO(n)所以建堆的时间复杂度就是 O(n)。
2. 排序
建堆结束之后数组中的数据已经是按照大顶堆的特性来组织的。数组中的第一个元素就是堆顶也就是最大的元素。我们把它跟最后一个元素交换那最大元素就放到了下标为 n 的位置。当堆顶元素移除之后我们把下标为 n 的元素放到堆顶然后再通过堆化的方法将剩下的 n−1 个元素重新构建成堆。堆化完成之后我们再取堆顶的元素放到下标是 n−1 的位置一直重复这个过程直到最后堆中只剩下标为 1 的一个元素排序工作就完成了。 现在我们再来分析一下堆排序的时间复杂度、空间复杂度以及稳定性。 整个堆排序的过程都只需要极个别临时存储空间所以堆排序是原地排序算法。堆排序包括建堆和排序两个操作建堆过程的时间复杂度是 O(n)排序过程的时间复杂度是 O(nlogn)所以堆排序整体的时间复杂度是 O(nlogn)。 堆排序不是稳定的排序算法因为在排序的过程存在将堆的最后一个节点跟堆顶节点互换的操作所以就有可能改变值相同数据的原始相对顺序。
解答开篇
在实际开发中为什么快速排序要比堆排序性能好 我觉得主要有两方面的原因。第一点堆排序数据访问的方式没有快速排序友好。 对于快速排序来说数据是顺序访问的。而对于堆排序来说数据是跳着访问的。以这样对 CPU 缓存是不友好的。
第二点对于同样的数据在排序过程中堆排序算法的数据交换次数要多于快速排序。 对于基于比较的排序算法来说整个排序过程就是由两个基本的操作组成的比较和交换或移动。快速排序数据交换的次数不会比逆序度多。但是堆排序的第一步是建堆建堆的过程会打乱数据原有的相对先后顺序导致原数据的有序度降低。比如对于一组已经有序的数据来说经过建堆之后数据反而变得更无序了。
内容小结
堆是一种完全二叉树。它最大的特性是每个节点的值都大于等于或小于等于其子树节点的值。因此堆被分成了两类大顶堆和小顶堆。 堆中比较重要的两个操作是插入一个数据和删除堆顶元素。这两个操作都要用到堆化。插入一个数据的时候我们把新插入的数据放到数组的最后然后从下往上堆化删除堆顶数据的时候我们把数组中的最后一个元素放到堆顶然后从上往下堆化。这两个操作时间复杂度都是 O(logn)。 堆排序包含两个过程建堆和排序。我们将下标从 1/2n 到 1 的节点依次进行从上到下的堆化操作然后就可以将数组中的数据组织成堆这种数据结构。接下来我们迭代地将堆顶的元素放到堆的末尾并将堆的大小减一然后再堆化重复这个过程直到堆中只剩下一个元素整个数组中的数据就都有序排列了。
相关文章：
