java - 斐波那契堆问题

Question

我已经在 J​​ava 中使用 Fibonacci 堆实现大约一个星期了。它是基于 CLRS 书籍的实现。

我想看看与 Java 的默认 PriorityQueue 相比，在我正在处理的副项目中使用它是否会获得任何性能提升。 [Java 中的默认实现是基于数组的，因此更加本地化。尽管复杂度更高，但它仍可能优于 F-Heap]。

我的问题似乎源于移除 min 元素后堆的合并部分。我不断抛出 arrayindexoutofboundsexceptions。特别是在 while 循环中，当它合并所有具有相同度数的节点时。它超出了 D() 函数设置的界限。

所以要么是我的 D() 函数错了，我不认为是错的，要么是发生了其他事情。很可能与副作用有关。

代码位于here .幸运的是，我已经尝试调试了大约一周。我是否遗漏了一些明显的东西？

Answer 1

您需要检查分析，因为我不确定节点度数的上限是否不应该是地板。在您的 D 函数中，您对 int 的转换会截断小数部分。将其更改为舍入似乎可以清除索引越界错误。

不过似乎还有一个问题。我没有追查什么条件，但子列表最终可能没有标记集。这会导致循环遍历子列表时 removeMin 中的无限循环，因为它们是循环的。