斐波那契堆EXTRACT-MIN操作标记属性不一致及CLRS摊还分析疑问

一、为啥DECREASE-KEY和EXTRACT-MIN对mark属性的处理不一样？ #

先搞清楚mark属性的核心作用：标记非根节点是否已经丢过至少一个子节点，这个标记是用来触发级联切断的——当一个非根节点丢第二个子节点时，它会被切断并移到根列表，同时标记它的父节点。

• DECREASE-KEY里的切断：节点x因为键值变小被父节点切断，移到根列表后成了根节点。根节点没有父节点，以后就算丢子节点，也不会触发针对父节点的级联切断，所以它的mark属性没用了，直接设成FALSE很合理。说白了，根节点不需要标记，因为没人会因为它丢子节点来切它。
• EXTRACT-MIN里的子节点迁移：最小节点的子节点被移到根列表，不是因为父节点主动切它们（父节点直接被删了），这些节点之前的mark是记录它们当子节点时有没有丢过子节点。要是以后它们被挂到其他节点下面当子节点，这个标记依然有用——再丢子节点就会触发级联切断。所以没必要改它们的mark，留着原状态就行。

这俩处理逻辑其实是一致的，都是看节点角色变了之后mark还有没有用，根本不存在啥不一致。

二、CLRS里EXTRACT-MIN的摊还分析势能计算错了吗？ #

结论：没错误，是合理的上界估计。

先回忆下关键信息：势能函数是$\Phi(H) = t(H) + 2m(H)$，其中$t(H)$是根列表里树的数量，$m(H)$是堆里被标记的节点数。

拆解操作前后的势能变化：

1. 删掉最小节点后，把它的所有子节点加到根列表，这时候根的数量$t(H)$会增加（加的数量等于最小节点的度数）。
2. 接下来合并度数相同的根节点，最后根的数量最多是$D(n)+1$（$D(n)$是n节点斐波那契堆的最大度数，因为合并后每个度数对应的根最多一个，所以根的数量不会超过这个数）。
3. 再看标记节点数$m(H)$：操作里只有链接操作会改mark属性——每次链接会把被挂成子节点的那个节点的mark设为FALSE。要是这个节点之前是标记的，$m(H)$就会减少；但操作里没有任何节点被标记，所以操作后的$m(H')$肯定小于等于操作前的$m(H)$。

CLRS原文说“之后的势能至多为$(D(n)+1)+2m(H)$”，这里用操作前的$m(H)$代替操作后的$m(H')$，是因为$2m(H') \leq 2m(H)$，用原$m(H)$算出来的是势能的上界，完全符合摊还分析求最坏情况上界的需求。所以这个计算是对的，没毛病。

内容的提问来源于stack exchange，提问作者Preetom Saha Arko