斐波那契堆问题
我用 Java 实现斐波那契堆已经大约一周了。这是基于 CLRS 书籍的实现。
我想看看与 Java 的默认 PriorityQueue 相比，在我正在进行的副项目中使用它是否会获得任何性能提升。 [Java 中的默认实现是基于数组的，因此更加本地化。尽管复杂性更高，但它的性能仍可能优于 F-Heap]。
我的问题似乎源于删除最小元素后堆的合并部分。我不断抛出 arrayindexoutofboundsExceptions 。特别是在 while 循环中，当它合并具有相同度数的所有节点时。它超出了 D() 函数设置的界限。
所以要么我的 D() 函数是错误的（我不认为是错误的），要么是发生了其他事情。最有可能与副作用有关。
代码位于此处。我已经尝试调试这个大约一周了，现在运气好。我错过了一些明显的东西吗？
I've been working on a Fibonacci Heap implementation in Java for about a week now. It's the implementation based off of the CLRS book.
I wanted to see if I would get any performance boost using it in a side project I'm working on compared to Java's default PriorityQueue. [The default implementation in Java is array based, so much more local. It may still outperform the F-Heap despite higher bounds in complexity].
My issue seems to stem from the consolidate part of the heap after removing the min element. I keep getting arrayindexoutofboundsexceptions thrown. Specifically in the while loop, when it is consolidating all nodes that have the same degree. It is exceeding the bounds set by the D() function.
So either my D() function is wrong, which, I don't think it is, or something else is happening. Most likely side effect related.
The code is located here. I've been trying to debug this for about week with now luck. Am I missing something obvious?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
您需要检查分析，因为我不确定节点度数的上限是否不应该是下限。在 D 函数中，转换为 int 会截断小数部分。将其更改为舍入似乎可以清除索引越界错误。
但似乎还有一个额外的问题。我没有追查什么条件，但子列表最终可能没有哨兵集。由于子列表是循环的，这会导致在循环子列表时在removeMin中出现无限循环。
You will need to check the analysis since I'm not sure if the upper bound of the node degree should not be the floor. In your D function, your cast to int is truncating the decimal portion. Changing this to rounding seems to clear up the index out of bounds error.
There seems to be an additional problem though. I didn't track down what conditions but child lists can end up not having a sentinal set. This leads to an infinite loop in removeMin when looping through the child list since they are circular.