斐波那契堆問題

Question

我一直在使用Java的斐波那契堆實現約一週。這是基於CLRS書籍的實現。

我想看看是否可以在我正在開發的一個側項目中使用它，而不是使用Java的默認PriorityQueue。 [Java中的默認實現是基於數組的，更多的是本地的。儘管複雜程度越來越高，它仍可能超越F堆。

我的問題似乎源於去除min元素後合併部分的堆。我一直在拋出arrayindexoutofboundsexceptions。特別是在while循環中，當它合併具有相同程度的所有節點時。它超出了D（）函數設置的界限。

因此，無論我的D（）函數是錯誤的，我不認爲它，或其他事情正在發生。最有可能的副作用相關。代碼here。我一直試圖調整這一週，現在運氣好。我錯過了明顯的東西嗎？

Answer 1

您將需要檢查分析，因爲我不確定節點度數的上限是否應該不是最低限度。在你的D函數中，你的轉換爲int將截斷小數部分。將此更改爲四捨五入似乎可以清除索引越界錯誤。

雖然似乎還有一個額外的問題。我沒有找到什麼條件，但是兒童名單可能最終沒有一個名單。由於循環遍歷子列表，這會導致removeMin中的無限循環，因爲它們是循環的。