data-structures - 标记斐波那契堆中某些节点的目的是什么？

Question

这张来自维基百科文章的图片有一个斐波那契堆的三个节点，标记为蓝色。在这个数据结构中标记一些节点的目的是什么？

Answer 1

直观地说，斐波那契堆维护着一组不同顺序的树，当删除最小值发生时将它们合并。构建斐波那契堆的希望是每棵树都拥有大量节点。每棵树中的节点越多，需要存储在树中的树的数量就越少，因此在每个删除分钟上合并树所花费的时间就越少。

同时，斐波那契堆试图使递减键操作尽可能快。为此，斐波那契堆允许子树从其他树中“切出”并移回根部。这使得减少键更快，但使每棵树拥有更少的节点（并且也增加了树的数量）。因此，设计结构中存在基本张力。

为了使它起作用，斐波那契堆中的树的形状必须有所限制。直观地说，斐波那契堆中的树是允许丢失少量孩子的二叉树。具体来说，斐波那契堆中的每棵树最多允许丢失两个孩子，然后该树需要在后面的步骤“重新处理”。斐波那契堆中的标记步骤允许数据结构计算到目前为止丢失了多少孩子。未标记的节点没有丢失任何子节点，而标记的节点丢失了一个子节点。一旦一个标记节点失去了另一个孩子，它就失去了两个孩子，因此需要移回根列表进行重新处理。

许多介绍性算法教科书记录了为什么这项工作的细节。这一点都不明显，而且数学有点棘手。

希望这提供了一个有用的直觉！

Answer 2

当其子节点之一由于减少键而被剪切时，节点被标记。当第二个孩子被切割时，该节点也会从其父节点切割自己。标记已完成，以便您知道第二次切割何时发生。

Answer 3

来自Wiki的很好的解释：操作减少键将取节点，减少键，如果违反堆属性（新键小于父键），则从其父节点中删除节点。如果父级不是根，则对其进行标记。如果它已经被标记，它也会被剪切并标记它的父节点。我们继续向上直到到达根节点或未标记的节点。现在，如果它是新的最小值，我们将最小值指针设置为减小的值。