伪代码来自 Introduction to Algorithms 指出:
for each node w in the root list of H
link trees of the same degree
但是如何高效地实现for each root node部分呢?原始根在整个合并过程中都与同级的其他根相连,这使得仅通过根节点的循环列表变得困难。我如何确定我是否检查了每个根节点?
最佳答案
执行此操作的一种简单方法是使用三步流程:
- 打破循环链接,使列表现在只是一个普通的双向链接列表。
- 遍历双向链表并处理每棵树。这很棘手,因为正如您所提到的,每个节点上的 forward 和 next 指针在迭代过程中可能会发生变化。
- 关闭循环。
以下是您可以执行每个步骤的方式:
打破循环链接:
rootList->prev->next = NULL;
rootList->prev = NULL;
遍历双向链表。
Node* current = rootList;
while (current != NULL) {
/* Cache the next node to visit so that even if the list changes, we can still
* remember where to go next.
*/
Node* next = current->next;
/* ... main Fibonacci heap logic ... */
current = next;
}
修复双向链表:
Node* curr = rootList;
if (curr != NULL) { // If list is empty, no processing necessary.
while (curr->next != NULL) {
curr = curr->next;
}
curr->next = rootList;
rootList->prev = curr;
}
希望这对您有所帮助!
关于algorithm - 在 Fibonacci 堆中实现 Consolidate,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/15185208/