安塔的二项堆&斐波那契堆学习笔记

# 前言 [总前言](https://www.luogu.org/blog/Atalod/learning-note-pre) 安塔感觉自己的技能树点偏了QwQ。 upd（2019/9/20）：修改逻辑和讲解顺序，删除不完全证明。由于该文章是一个半月以前写成的（那时候我比现在菜很多，文风也更加跳脱），并且是学习笔记性质（即边学习边写文），难免有逻辑混乱或者不当之处。敬请指出。 # 左偏堆 众所周知，合并平衡树（安塔学过的）最靠谱的方法就是启发式合并——将小的平衡树的结点一个一个地插到大的里面。均摊时间复杂度可以被认为是$\Theta(\log^2 n)$的。 但是，对于堆，有左偏堆这种东西，可以在$\Theta(\log n)$的时间内合并两个堆。 究其原因，是因为堆可以任意交换子节点。堆的限制条件比BST弱很多，只要满足其子节点的键值都小于其父节点就可以了（以大根堆为例）。 既然限制条件比较少，就可以做出种种灵活的调整，带来更优的复杂度以及更快速的操作。当然，堆可支持的操作相应的也比平衡树少（QwQ）。 # 二项堆 除了堆的子节点相互之间无序以外，堆还可以不限制子节点的数量。对于一个平衡树，如果你的一个节点有`x`颗子树，那你必须要在节点里包含`x-1`个键值来正确索引。但是，堆就没有这个限制。 注：平衡树可以将子节点数量纳入规则里面来达到平衡，例如`2-3树`和`B树`（`2-3树`是B树的一个特例，红黑树可以看做是2-3树的实现） 也就是说，我们可以简单地往堆的一个节点上堆子节点而不用担心破坏堆的性质（虽然如果子节点堆太多的话删根的时候搞死你），这就让我们想到了堆的合并。 > 既然我们有了一个性质，我们就得把这个性质玩出花来 ——我还是不知道是谁说的 假设： 1. 你手上有一个堆，有一个节点。 2. 有人给了你一个节点，你将两个节点合在了一起。 3. 又有人给你了两个节点，你直接找到一个小的根，一并挂上去。 4. 这回有人给了你四个节点，你还是在这两个各有四个节点的根里面找到一个最小的根，然后一股脑全挂上去。 5. 那人给了你八个节点，你厌烦了，把树甩他脸上就走人了，继续看博客。 ~~鲁智深倒拔二项树~~ 与图片一起食用可以获得更好的理解：  以上就叫二项树啦，恭喜你新数据结构get√。 随手口糊+推一下，可以发现以下性质： + 第$k$个二项树有$2^k$个结点（请再次看一遍扔树过程） + 第$n$个二项树中深度为$k$的结点有$C_n^k$个（命名由来，数数就知道了，虽然没啥用） + 可以在$\Theta(1)$的时间内合并两个相同的满足堆性质的二项树 但是，有个小问题： $$\text{我们似乎搞不到一个有任意节点的二项树}$$ 没事，即使 ~~洛谷臭名昭~~ 我们搞不到一个有任意节点的二项树，但是我们搞得到一堆二项树让他们的节点数合起来是任意的。 比如如果我们想搞到一堆拢共有七个节点的二项树，我们可以`1+1+1+2+2`，可以`2+2+1+2`，也可以`1+2+4`（幼儿园奥数题），显然，每个数字最少可以拆分成$\Theta(\log n)$个二项树。 ~~一堆二项树，就叫二项堆。~~ 在某些方面退让，某些方面严格，舍弃一些不重要的性质，换取一些能够大大加快速度的性质。这就是0/1背包模板题啊QwQ。 而二项堆的性质有： + 最多由$\Theta(\log n)$个满足堆性质的二项树组成 + 相同大小的二项树只有一个 接下来就是操作啦！ ## 插入节点 一般而言，可并堆的插入就一句话：将新结点视为一个只有一个结点的堆，执行堆的合并。 所以这里就先略过啦QwQ。 ## 合并两个二项堆 ~~既然两个都是一堆，那我们直接把两堆扫到一起吧。~~ 直接合并的话几乎肯定会破坏性质2，所以我们需要从下往上扫一遍，遇见有相同大小的就合掉。你想到了什么？二进制加法？对，就是这个。 复杂度是超级经典的$\Theta(\log n)$。 ## 查找最小数 维护一个指针就好啦，时间复杂度$\Theta(1)$。 ## 删除一个最小数 拢共分两步： 1. 找到那个最小数（肯定是某个二项堆的根节点）。 2. 暴力去掉，把子节点都拆出来倒一起。 3. 倒出来的子节点当做一个新堆与原堆合并。 时间复杂度$\Theta(1+1+\log n)=\Theta(\log n)$ ~~十分暴力。~~ ## 调整某个数的权值 这个在某一个二项堆里面进行内部消化就好啦。能上浮上浮，不能上浮**就从大的孩子开始往小的找**，这样每次比较都能够排除一半的待比较集合，时间复杂度$\Theta(\log n)$ # 列表比较 作为一个阶段性成果，我们有幸邀请到了**朴素堆**、**左偏堆**和**二项堆**作为嘉宾，来列一张时间复杂度表庆祝一下。 |名称|插入|查找最小值|删除最小值|合并两堆|调整某个数的权值| |---|---|---|---|---|---| |朴素堆|$\Theta(\log n)$|$\Theta(1)$|$\Theta(\log n)$|$\Theta(\log^2n)$|$\Theta(\log n)$| |左偏堆|$\Theta(\log n)$|$\Theta(1)$|$\Theta(\log n)$|$\Theta(\log n)$|$\Theta(\log n)$| |二项堆|$\Theta(\log n)$|$\Theta(1)$|$\Theta(\log n)$|$\Theta(\log n)$|$\Theta(\log n)$| emmmm……这张表有点单调QwQ。 ~~谁叫这些都是这么优秀的数据结构~~ # 斐波那契堆 接下来，就是装大佬利器斐波那契堆啦。 为什么说是装呢？ 因为……它太简单辣QwQ。 新的数据结构必然有新的性质。斐波那契堆舍弃了二项堆的二项树结构，而……直接放开生孩子！每个节点的孩子个数没有任何限制！节点长得非常狂野奔放！用一个大大的双向循环链表串起整个堆！  ~~这是个象征着自由的数据结构~~ 当然，斐波那契堆虽然理论时间复杂度得到了改善，但是它常数太大了，以至于能够用它的场合都能用二项堆来替代。所以，**其在OI中没有任何实际价值**。 但是还记得前言吗？ > 安塔感觉自己的技能树点偏了QwQ。 ## 插入 同样，斐波那契堆的插入操作就一句话： $$\text{将新结点视为一个只有一个结点的堆，执行堆的合并。}$$ ## 合并两个斐波那契堆 还记得我们说斐波那契堆是个象征着自由的数据结构吗？ 很好，你还记得。 那你可以直接跳过这一节了，因为这一节的东西实在太简单，你肯定会。我们不是用一个循环链表表示一个斐波那契堆吗？串一起就好了。 ## 查找最小数 讲道理，哪一个堆不是维护一个指针指向最小数然后轻松$\Theta(1)$搞定的？ ## 删除一个最小数 ~~自由的代价来了~~ 首先，我们删除那个最小数，然后将它的孩子们全部倒一起堆到根表（就是最大的那个双向链表）里面。 但是，我们不可能就这么拍拍屁股走人，我们需要更新那个最小数指针。 然后你会发现，如果按照上述狂野奔放的操作的话，我们的斐波那契堆会退化成斐波那契双向链表，根表里面节点的数量最多可能达到$\Theta(n)$。哦豁，完蛋。 所以，为了防止$\Theta(n^2)$惨剧出现，我们需要对一些散散的根节点进行一些合并。 参照二项堆的思路，合并的时候，只需要让每种堆只有一个就好了。二项堆里面是每种大小的堆只有一个，而我们这里让每种根节点的度数只有一个吧QwQ。 为什么？因为我们太自由了，不想维护太多信息。维护堆的大小就太严格了，所以就干脆直接维护度这种随手$\Theta(1)$维护的信息好了。 所以，我们直接扫一遍，发现有度相同的直接合并就好了。合并方式特别随意，根节点比一下，输了的丢赢家的孩子表里面去，颇有二项堆的风范。 ~~二项堆：我不是我没有，我没辣么自由，我还要将孩子从大到小排好~~ ## 调整某个节点的权值 ~~自由的代价愈发猖狂，话说我们可以不支持这个操作吗~~ 如果没有破坏堆的性质，那就可以直接`continue`了。但是，在树里面跳的话，会涉及到遍历孩子等一系列麻烦操作，很难保证$\Theta(\log n)$的时间复杂度。所以，必须要找一个不同的方式来调整节点的权值。 这里只讲向根调节，即，如果是大根堆的话，只支持向上调节，小根堆的话只支持向下调节。因为这个操作用的多啊QwQ，`Dijkstra`等等需要用堆的场合不都是向根调的吗（最主要的是反根调节作者不会 但是，斐波那契堆是象征着自由的数据结构，即使是最复杂的操作也十分简单暴力。我们找到那个节点，把它拧下来，丢到根表里面去。哦豁，$\Theta(1)$。 不久你会发现，这样乱搞是要付出代价的，因为这个算法~~明显十分可卡~~。 也就是说，如果用心卡一下，你的根表里面会充斥着$\Theta(\sqrt{n})$个根节点，占着各种度数。干的漂亮！我们成功地把一个堆变成了分块级的时间复杂度！ 所以，我们不能这么乱搞。如果无限制地拧下一个根节点里面的孩子，会让这个根节点的大小与度数严重失衡。解决方案也很简单粗暴，我们让一个节点不能失去太多的孩子，如果它失去的孩子多于一个，我们把它也给拧下来。 # 时间复杂度证明 定义一个势能函数$\Phi(t)=\text{t的根表的大小}$。 势能函数，是均摊时间复杂度证明的一种方式。如果一个操作会引起势能减少，我们就认为这个操作不占用时间。当然，势能函数不能定义成$\Phi(t)=\infty - \text{操作数}$，所以，势能在一开始必须为一个有限常数，并且，引起势能增加的操作都必须为势能的增加付出代价。 #### 插入/合并 插入和合并操作会使两个斐波那契堆的势能函数相加，因此不引起势能上升（我们不生产势能，我们只是势能的搬运工），所以仅消耗本身的常数时间。 $\Theta(1)$ #### 查找最小数 。 $\Theta(1)$ #### 删除最小数 随手分析就可以发现，$\text{合并操作的开销}=\text{开数组登记根节点的开销}+\text{合并的开销}$。其中，登记根节点的开销是由最多的度数不同的根节点个数决定的。 假设度为`k`的节点最少有$F_k$个子节点。 度为`k+1`的节点可以被拆分成两个部分：一个度为`k`的节点和其最大的一个子树。由于子树最多损失一个节点，所以子树的度最少为`k-1`，即： $$F_{k+1}=F_k+F_{k-1}$$ 我们就成功证明了： $$f(i)\geq Fib(i)$$ 其中$Fib(i)$表示斐波那契数列的第i项。 然后回顾一下斐波那契数列的通项公式： $$f(i)\geq Fib(i) = \frac{(\frac{1+\sqrt{5}}{2})^n-(\frac{1-\sqrt{5}}{2})^n}{\sqrt{5}}$$ 所以说，$\Theta(f(i))\approx\Theta(1.618^i)$，斐波那契数列的增长速度是$\Theta(\log n)$的。 由此，需要登记的根节点最大只有$\Theta(\log n)$种。 再考虑合并的开销。合并的时候，我们可能会有$\Theta(n)$个根结点，但是每次合并仅花费常数时间，还都会使势能函数减少1。则，合并所用时间可以视为由势能支付，可以看做不消耗时间。 因此，我们的时间是$\Theta(\log n)$。 #### 调整堆的权值 很显然，我们要做的仅仅是拧下来-检查父节点，时间复杂度是$\Theta(1)$的。 如果一颗斐波那契堆上面的一条路径都打上了标记，这时候再拧下最低端的一个节点，会导致路径上的点一个个被拧下来。这里就把调整操作为$\Theta(1)$的证明留给读者（~~因为作者懒~~）。 # 分析&应用 斐波那契堆可以看做是一个自由的二项堆。斐波那契堆对根表的限制十分随意，等到删除的时候才合并根表。这里就用了类似于线段树的`lazy tag`一样的思想。（我叫他`lazy algorithm`） 虽然斐波那契堆的时间复杂度有大片$\Theta(1)$，但是其本质是将大多数耗时的操作堆到合并根表的时候完成，所以运行时间没有大幅度的提高。反而会因为斐波那契数列的`logn`不如二项堆的`logn`严格而使常数变大。 同时，斐波那契堆由于其在单个操作上响应时间太长，因此不适合在实时场景（如游戏）中使用。~~但是挺适合在OI中使用~~ `Lazy algorithm`能够加快运行效率的本质是因为多个相同操作可以合并，或者可以避免建立结构之后再反复调整，进一步的本质是去时序化。例如线段树的区间加，就可以将两次区间加堆到一起完成。而斐波那契堆的`lazy algorithm`可以减少的重复运算主要是在调整节点权值的时候进行的。如果先建立堆结构再调整节点权值的话，需要对堆结构进行维护，斐波那契堆则避免了对堆结构的维护。 什么算法需要反复地调整堆里面的数值？ `Dijkstra`啊！ 所以，斐波那契堆优化的`Dijkstra`能够达到$\Theta(n\log n+m)$的效率。相比之下，线段树优化只能达到$\Theta((n+m)\log n)$，而`stl::priority_queue`优化的`Dijkstra`只能达到$\Theta((n+m)\log m)$。 # 最终表 |名称|插入|查找最小值|删除最小值|合并两堆|调整某个数的权值（向根调节）| |---|---|---|---|---|---| |朴素堆|$\Theta(\log n)$|$\Theta(1)$|$\Theta(\log n)$|$\Theta(\log^2n)$|$\Theta(\log n)$| |左偏堆|$\Theta(\log n)$|$\Theta(1)$|$\Theta(\log n)$|$\Theta(\log n)$|$\Theta(\log n)$| |二项堆|$\Theta(\log n)$|$\Theta(1)$|$\Theta(\log n)$|$\Theta(\log n)$|$\Theta(\log n)$| |斐波那契堆|$\Theta(1)$|$\Theta(1)$|$\Theta(\log n)$|$\Theta(1)$|$\Theta(1)$| # 参考文献 [这里有超多好看的图片QwQ](https://www.cs.princeton.edu/~wayne/teaching/fibonacci-heap.pdf)