Fibonacci堆或Brodal隊列在實踐中使用嗎？

Question

是否在任何地方使用斐波納契堆？我環顧四周，找到了相關問題的答案（見下文），但實際上沒有什麼能夠回答這個問題。

1. There are good implementations of Fibonacci heaps out there, including in standard libraries such as Boost C++.事實上，這些庫包含斐波那契堆表明它們必須在某處有用。
2. 我們知道斐波那契堆的某些條件需要在實踐中加快實現：「to benefit from Fibonacci heaps in practice, you have to use them in an application where decrease_keys are incredibly frequent」; 「For the Fibonacci Heap to really shine, you need either of the following cases: a) Expensive comparisons: Fib Heaps minimize the number of comparisons required to organize the data. b) The majority of operations is updateKey/insert/delete. As Fibonacci Heaps 'group' the updates together until the next extractMin, the larger the 'batch', the more efficient it gets.」
3. There is a data structure called a "Brodal Queue" which I'm not sure I'd heard of before that seems to have time complexity behaviors at least as good as Fibonacci heaps.Here是一個很好的表格，可以比較不同堆棧的各種操作的時間複雜度。
4. 在a question about whether there are any applications of Fibonacci or binomial heaps，回答者只給出了二項堆的例子。

Answer 1

據我所知，沒有實際使用斐波那契堆或Brodal隊列的主要應用程序。 Fibonacci堆最初設計用於滿足理論而不是實際需要：漸近地加速Dijkstra的最短路徑算法。 Brodal隊列（以及相關的功能數據結構）的設計類似於滿足理論保證，具體來說，是爲了回答關於是否有可能將Fibonacci堆的時間範圍與最壞情況保證相比較而不是攤銷保證的長期懸而未決的問題。從這個意義上說，數據結構並不是爲滿足實際需要而開發的，而是爲了推進我們對算法效率極限的理論理解。據我所知，目前沒有算法在Fibonacci堆上使用Brodal隊列實際上會更好。

正如其他答案所指出的，隱藏在斐波那契堆或Brodal隊列中的常數因子非常高。他們需要在很多複雜的鏈表中連接很多指針，因此具有絕對可怕的引用位置，尤其是與標準二進制堆相比。這意味着，除非您有需要大量減少鍵操作的算法，否則它們在實踐中可能會在執行緩存效果時表現更差。有些情況下會出現這種情況（例如，鏈接的答案會談到其中的一些答案），但將它們視爲高度專業化的情況而不是常見用例。如果您正在處理巨大的圖表，則更常見的是使用其他技術來提高效率，例如對近期問題使用近似算法，更好的啓發式算法或使用底層數據的特定屬性的算法。

希望這會有所幫助！