189 8069 5689
这是数据结构类重新复习笔记的第 五 篇，同专题的其他文章可以移步：
金坛ssl适用于网站、小程序/APP、API接口等需要进行数据传输应用场景，ssl证书未来市场广阔！成为成都创新互联公司的ssl证书销售渠道，可以享受市场价格4-6折优惠！如果有意向欢迎电话联系或者加微信：13518219792（备注：SSL证书合作）期待与您的合作！
堆 （Heap）又称为 优先队列 （priority queue），在队列的基础上，堆允许所有队列中的元素不一定按照 先进先出 （FIFO）的规则进行，而是使得每个元素有一定的优先级，优先级高的先出队列。
优先队列至少存在两个重要的操作：
有几种简单而明显的方法实现优先队列。
二叉堆 （binary heap）是一种对于优先队列的实现，可以简称为堆
堆是一棵 完全二叉树 （complete binary tree），即所有节点都必须有左右两个子节点，除了最后一排元素从左向右填入，直到没有元素为止。
很显然，一棵高为h的完全二叉树有 2^h 到 2^(h+1)-1 个节点，即其高度为 logN 向下取整。
完全二叉树的好处在于其规律性，可以使用一个数组而不需要链表来表示
对于数组中任一位置 i 上的元素，其左儿子在位置 2i 上，右儿子在左儿子后的单元 (2i+1) 上，它的父亲则在位置 i/2 向下取整上。
因此，不仅不需要链，而且遍历该树所需要的操作也极简单，在大部分计算机上都可能运行得非常快。唯一问题是最大的堆的大小需要事先估计。
使操作可以快速执行的性质是 堆序性质 （heap-order property）：对于每一个节点X，X的父节点中的键小于等于X中的键，除没有父节点根节点外。
将待插入的元素首先放置在最后一个位置上，以保证他是一个完全二叉树，然后将该元素与其父节点（i/2向下取整）比较，如果比其父节点小，就将两者互换，互换后再和新的父节点比较，这种方式称为 上滤 （percolate up），得到一个小顶堆（min heap），如果比较的时候是较大的值向上走，就会得到一个大顶堆（max heap）
比如向一个小顶堆中插入元素14的操作：
找出、返回并删除最小元非常简单，最小元就是根节点处的元素，将其返回并删除。接下来是处理这个B。首先拿下最后一个元素X，如果元素X比B的两个子节点都小，可以直接将X插入到B的位置，如果X比B的两个子节点中的任意一个大，就不能插入，此时找到两个子节点中较小的那个放到B处，B转而移至这个子结点处。重复如上的步骤直到X可以插入B处为止。这个操作成为 下滤 （percolate down）
比如从一个小顶堆中删除根节点
decreaseKey(p, A) 操作减小在位置p处的元素的值，减少量为A，可以理解为调高了某个元素的优先级。操作破坏了堆的性质，从而需要上滤操作进行堆的调整。
increaseKey(p, A) 操作增加在位置p处的元素的值，增加量为A，可以理解为降低了某个元素的优先级。操作破坏了堆的性质，从而需要下滤操作进行堆的调整。
remove(p) 操作删除在堆中位置p处的节点，这种操作可以通过连续执行 decreaseKey(p, ∞) 和 deleteMin() 完成，可以理解马上删除某个一般优先级的元素
即将一个原始集合构建成二叉堆，这个构造过程即进行N次连续的 insert 操作完成
定理 ：包含 2^(h+1)-1 个节点且高度为h的理想二叉树（perfect binary tree）的节点的高度和为 2^(h+1)-1-(h+1)
d堆 （d-Heaps）是二叉堆的简单推广，它与二叉堆很像，但是每个节点都有d个子节点，所以二叉堆是d为2的d堆。d堆是完全d叉树。比如下边的一个3堆。
d堆比二叉堆浅很多，其insert的运行时间改进到 O(logdN) 。但是deleteMin操作比较费时，因为要在d个子节点中找到最小的一个，需要进行d-1次比较。d堆无法进行find操作，而且将两个堆合二为一是很困难的事情，这个附加操作为merge合并。
注意！ 在寻找节点的父节点、子节点的时候，乘法和除法都有因子d。如果d是一个2的幂，则可以通过使用二进制的 移位 操作计算，这在计算机中是非常省时间的。但是如果d不是一个2的幂，则使用一般的乘除法计算，时间开销会急剧增加。有证据显示，实践中，堆可以胜过二叉堆
这些高级的数据结构很难使用一个数据结构来实现，所以一般都要用到链式数据结构，这种结构可能会使得其操作变慢。
零路径长 （null path length）npl(X)：定义为从一个X节点到其不具有两个子节点的子节点的最短路径长，即具有0个或者1个子节点的节点npl=0，npl(null)=-1，任意节点的零路径长都比其各个子节点中零路径长最小值多1。
左式堆 （leftist heap）是指对于任意一个节点X，其左子节点的零路径长都大于等于其右子节点的零路径长。很显然，左式堆趋向于加深左路径。比如下边的两个堆，只有左边的是左式堆，堆的节点标示的是该节点的零路径长。
左式堆的实现中，需要有四个值：数据、左指针、右指针和零路径长。
定理 ：在右路径上有r个节点的左式堆必然至少有 2^r-1 个节点
merge 是左式堆的基本操作， insert 插入可以看成是一个单节点的堆与一个大堆的 merge ， deleteMin 删除最小值操作可以看成是首先返回、删除根节点，然后将根节点的左右子树进行 merge 。所以 merge 是左式堆的基本操作。
假设现在有两个非空的左式堆H1和H2，merge操作递归地进行如下的步骤：
例如如下的两个堆：
将H2与H1的右子树（8--17--26）进行merge操作，此时（8--17--26）和H2的merge操作中又需要（8--17--26）和H2的右子堆（7--37--18）进行merge操作……如此递归得到如下的堆：
然后根据递归的最外层（回到H1和H2的merge的第二步），将上边合并的堆成为H1的右子堆
此时根节点（3）处出现了左右子堆不符合左式堆的情况，互换左右子堆并更新零路径长的值
斜堆 （skew heap）是左式堆的自调节形式，实现起来极其简单。斜堆和左式堆的关系类似于伸展树和AVL树之间的关系。斜堆是具有堆序的二叉树，但是不存在对树的结构的现限制。不同于左式堆，关于任意结点的零路径长的任何信息都不保留。斜堆的右路径在任何时刻都可以任意长，因此，所有操作的最坏情形运行时间均为O(N)。然而，正如伸展树一样，可以证明对任意M次连续操作，总的最坏情形运行时间是 O(MlogN)。因此，斜堆每次操作的 摊还开销 （amortized cost）为O(logN)
斜堆的基本操作也是merge合并，和左式堆的合并相同，但是不需要对不满足左右子堆的左式堆条件的节点进行左右子堆的交换。斜堆的交换是无条件的，除右路径上所有节点的最大者不交换它的左右儿子外，都要进行这种交换。
比如将上述的H1和H2进行merge合并操作
首先进行第一步，除了交换左右子树的操作与左式堆不同，其他的操作都相同
将合并的堆作为H1的右子堆并交换左右子堆，得到合并后的斜堆
二项队列 （binomial queue）支持merge、insert和deleteMin三种操作，并且每次操作的最坏情形运行时间为O(logN)，插入操作平均花费常数时间。
二项队列不是一棵堆序的树，而是堆序的树的集合，成为 森林 （forest）。堆序树中的每一棵都是有约束的 二项树 （binomial tree）。二项树是每一个高度上至多存在一棵二项树。高度为0的二项树是一棵单节点树，高度为k的二项树Bk通过将一棵二项树Bk-1附接到另一棵二项树Bk-1的根上而构成的。如下图的二项树B0、B1、B2、B3和B4。
可以看到二项树Bk由一个带有儿子B0，B1，……，Bk-1的根组成。高度为k的二项树恰好有2^k个节点，而在深度d处的节点数为二项系数Cdk。
我们可以使用二项树的集合唯一地表示任意大小的优先队列。以大小为13的队列为例，13的二进制表示为1101，从而我们可以使用二项树森林B3、B2、B0表示，即二进制表示的数中，第k位为1表示Bk树出现，第k位为0表示Bk树不出现。比如上述的堆H1和堆H2可以表示为如下的两个二项队列：
二项队列额merge合并操作非常简单，以上边的二项队列H1、H2为例。需要将其合并成一个大小为13的队列，即B3、B2、B0。
首先H2中有一个B0，H1中没有，所以H2中的B0可以直接作为新的队列的B0的树
其次H1和H2中两个B1的树可以合并成一个新的B2的树，只需要将其中根节点较小的堆挂到根节点较大的堆的根节点上。这样就得到了三棵B2堆，将其中根节点最大的堆直接放到新队列中成为它的B2堆。
最后将两个B2堆合并成一个新队列中的B3堆。
二项队列的deleteMin很简单，只需要比较队列中所有二项堆的根节点，返回和删除最小的值即可，时间复杂度为O(logN)，然后进行一次merge操作，也可以使用一个单独的空间每次记录最小值，这样就可以以O(1)的时间返回。
森林中树的实现采用“左子右兄弟”的表示方法，然后二项队列可以使用一个数组来记录森林中每个树的根节点。
例如上边的合成的二项队列可以表示成如下的样子：
STL中，二叉堆是通过 priority_queue 模板类实现的，在头文件 queue 中，STL实现一个大顶堆而不是小顶堆，其关键的成员函数如下：
堆排序是一种原地的、时间复杂度为 O(nlogn) 的排序算法。
堆是一种特殊的树。
只要满足这两点，它就是一个堆：
对于每个节点的值都大于等于子树中每个节点值的堆，我们叫做 “大顶堆” 。对于每个节点的值都小于等于子树中每个节点值的堆，我们叫做 “小顶堆” 。
完全二叉树比较适合用数组来存储。用数组来存储完全二叉树是非常节省存储空间的。下标可以直接计算出左右字数的下标。（数组中下标为 i 的节点，左子节点下标为 i∗2 ，右子节点下标为 i∗2+1，父节点的下标为 i/2 。）
如果我们把新插入的元素放到堆的最后，你可以看我画的这个图，是不是不符合堆的特性了？于是，我们就需要进行调整，让其重新满足堆的特性，这个过程我们起了一个名字，就叫做 堆化（heapify） 。
堆化实际上有两种，从下往上和从上往下。这里我先讲从下往上的堆化方法。
堆化非常简单，就是顺着节点所在的路径，向上或者向下，对比，然后交换。
我们把最后一个节点放到堆顶，然后利用同样的父子节点对比方法。对于不满足父子节点大小关系的，互换两个节点，并且重复进行这个过程，直到父子节点之间满足大小关系为止。这就是 从上往下的堆化方法 。
一个包含 n 个节点的完全二叉树，树的高度不会超过 log2n。堆化的过程是顺着节点所在路径比较交换的，所以堆化的时间复杂度跟树的高度成正比，也就是 O(logn)。插入数据和删除堆顶元素的主要逻辑就是堆化，所以，往堆中插入一个元素和删除堆顶元素的时间复杂度都是 O(logn)。
这里我们借助于堆这种数据结构实现的排序算法，就叫做堆排序。这种排序方法的时间复杂度非常稳定，是 O(nlogn)，并且它还是原地排序算法。
从后往前处理数组，并且每个数据都是从上往下堆化。
因为叶子节点往下堆化只能自己跟自己比较，所以我们直接从最后一个非叶子节点开始，依次堆化就行了。
建堆的时间复杂度就是 O(n)。 推导过程见 极客时间--数据结构与算法之美
建堆结束之后，数组中的数据已经是按照大顶堆的特性来组织的。数组中的第一个元素就是堆顶，也就是最大的元素。我们把它跟最后一个元素交换，那最大元素就放到了下标为 n 的位置。
这个过程有点类似上面讲的“删除堆顶元素”的操作，当堆顶元素移除之后，我们把下标为 n 的元素放到堆顶，然后再通过堆化的方法，将剩下的 n−1 个元素重新构建成堆。堆化完成之后，我们再取堆顶的元素，放到下标是 n−1 的位置，一直重复这个过程，直到最后堆中只剩下标为 1 的一个元素，排序工作就完成了。
整个堆排序的过程，都只需要极个别临时存储空间，所以堆排序是原地排序算法。堆排序包括建堆和排序两个操作，建堆过程的时间复杂度是 O(n)，排序过程的时间复杂度是 O(nlogn)，所以，堆排序整体的时间复杂度是 O(nlogn)。
堆排序不是稳定的排序算法，因为在排序的过程，存在将堆的最后一个节点跟堆顶节点互换的操作，所以就有可能改变值相同数据的原始相对顺序。
堆这种数据结构几个非常重要的应用：优先级队列、求 Top K 和求中位数。
假设我们有 100 个小文件，每个文件的大小是 100MB，每个文件中存储的都是有序的字符串。我们希望将这些 100 个小文件合并成一个有序的大文件。这里就会用到优先级队列。
这里就可以用到优先级队列，也可以说是堆。我们将从小文件中取出来的字符串放入到小顶堆中，那堆顶的元素，也就是优先级队列队首的元素，就是最小的字符串。我们将这个字符串放入到大文件中，并将其从堆中删除。然后再从小文件中取出下一个字符串，放入到堆中。循环这个过程，就可以将 100 个小文件中的数据依次放入到大文件中。
我们可以用优先级队列来解决。我们按照任务设定的执行时间，将这些任务存储在优先级队列中，队列首部（也就是小顶堆的堆顶）存储的是最先执行的任务。
如何在一个包含 n 个数据的数组中，查找前 K 大数据呢？我们可以维护一个大小为 K 的小顶堆，顺序遍历数组，从数组中取出数据与堆顶元素比较。如果比堆顶元素大，我们就把堆顶元素删除，并且将这个元素插入到堆中；如果比堆顶元素小，则不做处理，继续遍历数组。这样等数组中的数据都遍历完之后，堆中的数据就是前 K 大数据了。
中位数，顾名思义，就是处在中间位置的那个数。
使用两个堆：一个大顶堆， 一个小顶堆。 小顶堆中的数据都大于大顶堆中的数据。
如果新加入的数据小于等于大顶堆的堆顶元素，我们就将这个新数据插入到大顶堆；否则，我们就将这个新数据插入到小顶堆。
也就是说，如果有 n 个数据，n 是偶数，我们从小到大排序，那前 2n 个数据存储在大顶堆中，后 2n 个数据存储在小顶堆中。这样，大顶堆中的堆顶元素就是我们要找的中位数。如果 n 是奇数，情况是类似的，大顶堆就存储 2n+1 个数据，小顶堆中就存储 2n 个数据。
极客时间--数据结构与算法之美--28 | 堆和堆排序：为什么说堆排序没有快速排序快？
堆就是用数组实现的二叉树，所以它没有使用父指针或者子指针。堆根据“堆属性”来排序，“堆属性”决定了树中节点的位置。
堆的常用方法：
堆分为两种： 最大堆 和 最小堆 ，两者的差别在于节点的排序方式。
在最大堆中，父节点的值比每一个子节点的值都要大。在最小堆中，父节点的值比每一个子节点的值都要小。这就是所谓的“堆属性”，并且这个属性对堆中的每一个节点都成立。
例子：
这是一个最大堆，，因为每一个父节点的值都比其子节点要大。 10 比 7 和 2 都大。 7 比 5 和 1 都大。
根据这一属性，那么最大堆总是将其中的最大值存放在树的根节点。而对于最小堆，根节点中的元素总是树中的最小值。堆属性非常有用，因为堆常常被当做优先队列使用，因为可以快速地访问到“最重要”的元素。
堆并不能取代二叉搜索树，它们之间有相似之处也有一些不同。我们来看一下两者的主要差别：
节点的顺序。 在二叉搜索树中，左子节点必须比父节点小，右子节点必须必比父节点大。但是在堆中并非如此。在最大堆中两个子节点都必须比父节点小，而在最小堆中，它们都必须比父节点大。
内存占用。 普通树占用的内存空间比它们存储的数据要多。你必须为节点对象以及左/右子节点指针分配内存。堆仅仅使用一个数据来存储数组，且不使用指针。
平衡。 二叉搜索树必须是“平衡”的情况下，其大部分操作的复杂度才能达到 O(log n) 。你可以按任意顺序位置插入/删除数据，或者使用 AVL 树或者红黑树，但是在堆中实际上不需要整棵树都是有序的。我们只需要满足堆属性即可，所以在堆中平衡不是问题。因为堆中数据的组织方式可以保证 O(log n) 的性能。
搜索。 在二叉树中搜索会很快，但是在堆中搜索会很慢。在堆中搜索不是第一优先级，因为使用堆的目的是将最大（或者最小）的节点放在最前面，从而快速的进行相关插入、删除操作。
用数组来实现树相关的数据结构也许看起来有点古怪，但是它在时间和空间上都是很高效的。
我们准备将上面例子中的树这样存储：
就这么多！我们除了一个简单的数组以外，不需要任何额外的空间。
如果我们不允许使用指针，那么我们怎么知道哪一个节点是父节点，哪一个节点是它的子节点呢？问得好！节点在数组中的位置index 和它的父节点以及子节点的索引之间有一个映射关系。
如果 i 是节点的索引，那么下面的公式就给出了它的父节点和子节点在数组中的位置：
注意 right(i) 就是简单的 left(i) + 1 。左右节点总是处于相邻的位置。
我们将写公式放到前面的例子中验证一下。
复习一下，在最大堆中，父节点的值总是要大于（或者等于）其子节点的值。这意味下面的公式对数组中任意一个索引 i 都成立：
可以用上面的例子来验证一下这个堆属性。
如你所见，这些公式允许我们不使用指针就可以找到任何一个节点的父节点或者子节点。事情比简单的去掉指针要复杂，但这就是交易：我们节约了空间，但是要进行更多计算。幸好这些计算很快并且只需要 O(1) 的时间。
理解数组索引和节点位置之间的关系非常重要。这里有一个更大的堆，它有15个节点被分成了4层：
图片中的数字不是节点的值，而是存储这个节点的数组索引！这里是数组索引和树的层级之间的关系：
由上图可以看到，数组中父节点总是在子节点的前面。
注意这个方案与一些限制。你可以在普通二叉树中按照下面的方式组织数据，但是在堆中不可以：
在堆中，在当前层级所有的节点都已经填满之前不允许开是下一层的填充，所以堆总是有这样的形状：
小测验，假设我们有这样一个数组：
这是一个有效的堆吗？答案是 yes ！一个从低到高有序排列的数组是以有效的最小堆，我们可以将这个堆画出来：
堆属性适用于每一个节点，因为父节点总是比它的字节点小。（你也可以验证一下：一个从高到低有序排列的数组是一个有效的最大堆）
如果你好奇，这里有更多的公式描述了堆的一些确定属性。你不需要知道这些，但它们有时会派上用场。 可以直接跳过此部分！
树的 高度 是指从树的根节点到最低的叶节点所需要的步数，或者更正式的定义：高度是指节点之间的边的最大值。一个高度为 h 的堆有 h+1 层。
下面这个对的高度是3，所以它有4层：
如果一个堆有 n 个节点，那么它的高度是 h = floor(log2(n)) 。这是因为我们总是要将这一层完全填满以后才会填充新的一层。上面的例子有 15 个节点，所以它的高度是 floor(log2(15)) = floor(3.91) = 3 。
如果最下面的一层已经填满，那么那一层包含 2^h 个节点。树中这一层以上所有的节点数目为 2^h - 1 。同样是上面这个例子，最下面的一层有8个节点，实际上就是 2^3 = 8 。前面的三层一共包含7的节点，即： 2^3 - 1 = 8 - 1 = 7 。
所以整个堆中的节点数目为：* 2^(h+1) - 1*。上面的例子中， 2^4 - 1 = 16 - 1 = 15
叶节点总是位于数组的 floor(n/2) 和 n-1 之间。
有两个原始操作用于保证插入或删除节点以后堆是一个有效的最大堆或者最小堆：
shiftUp 或者 shiftDown 是一个递归的过程，所以它的时间复杂度是 O(log n) 。
基于这两个原始操作还有一些其他的操作：
上面所有的操作的时间复杂度都是 O(log n) ，因为 shiftUp 和 shiftDown 都很费时。还有少数一些操作需要更多的时间：
堆还有一个 peek() 方法，不用删除节点就返回最大值（最大堆）或者最小值（最小堆）。时间复杂度 O(1) 。
我们通过一个插入例子来看看插入操作的细节。我们将数字 16 插入到这个堆中：
堆的数组是： [ 10, 7, 2, 5, 1 ] 。
第一股是将新的元素插入到数组的尾部。数组变成：
相应的树变成了：
16 被添加最后一行的第一个空位。
不行的是，现在堆属性不满足，因为 2 在 16 的上面，我们需要将大的数字在上面（这是一个最大堆）
为了恢复堆属性，我们需要交换 16 和 2 。
现在还没有完成，因为 10 也比 16 小。我们继续交换我们的插入元素和它的父节点，直到它的父节点比它大或者我们到达树的顶部。这就是所谓的 shift-up ，每一次插入操作后都需要进行。它将一个太大或者太小的数字“浮起”到树的顶部。
最后我们得到的堆：
现在每一个父节点都比它的子节点大。
我们将这个树中的 (10) 删除：
现在顶部有一个空的节点，怎么处理？
当插入节点的时候，我们将新的值返给数组的尾部。现在我们来做相反的事情：我们取出数组中的最后一个元素，将它放到树的顶部，然后再修复堆属性。
现在来看怎么 shift-down (1) 。为了保持最大堆的堆属性，我们需要树的顶部是最大的数据。现在有两个数字可用于交换 7 和 2 。我们选择这两者中的较大者称为最大值放在树的顶部，所以交换 7 和 1 ，现在树变成了：
继续堆化直到该节点没有任何子节点或者它比两个子节点都要大为止。对于我们的堆，我们只需要再有一次交换就恢复了堆属性：
绝大多数时候你需要删除的是堆的根节点，因为这就是堆的设计用途。
但是，删除任意节点也很有用。这是 remove() 的通用版本，它可能会使用到 shiftDown 和 shiftUp 。
我们还是用前面的例子，删除 (7) :
[图片上传失败...(image-d46ac4-1534077058042)]
对应的数组是
你知道，移除一个元素会破坏最大堆或者最小堆属性。我们需要将删除的元素和最后一个元素交换：
最后一个元素就是我们需要返回的元素；然后调用 removeLast() 来将它删除。 (1) 比它的子节点小，所以需要 shiftDown() 来修复。
然而，shift down 不是我们要处理的唯一情况。也有可能我们需要 shift up。考虑一下从下面的堆中删除 (5) 会发生什么：
现在 (5) 和 (8) 交换了。因为 (8) 比它的父节点大，我们需要 shiftUp() 。