algorithm - 需要帮助了解如何减少斐波那契堆中的密钥

Question

我试图了解如何实现斐波那契堆操作。鉴于我们有以下堆：

例如，我们如何将 35 减少到 27？由于 27 不大于 30，因此没有保留顺序，因此我们必须重建堆。那么27去哪儿了？5岁以下？

Answer 1

在斐波那契堆中，reduce-key 实际上会从树中删除其键值低于父键值的任何节点。在您的情况下，该节点将作为单例节点放入根列表中。

更一般地说，减少键的工作原理如下：

1. 减小键。
2. 如果节点的新密钥大于其父节点的，则停止。
3. 如果节点是根节点，则停止。
4. 取消标记节点并将其从其父节点中删除。
5. 如果父项未标记，请标记它。
6. 如果父母被标记，请转到（3）。

希望这可以帮助！