Fibonacci 堆或 Brodal 队列在实践中是否在任何地方使用？
Are Fibonacci heaps or Brodal queues used in practice anywhere?
斐波那契堆在实践中是否在任何地方使用？我环顾四周，找到了相关问题的答案（见下文），但实际上没有什么能完全回答这个问题。
- There are good implementations of Fibonacci heaps out there, including in standard libraries such as Boost C++. 这些库包含斐波那契堆的事实表明它们一定在某些地方有用。
- 我们知道斐波那契堆在实践中需要满足某些条件才能更快：“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.”
- 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 很不错 table，比较了不同类型堆的各种操作的时间复杂度。
- 在a question about whether there are any applications of Fibonacci or binomial heaps，回答者只给出了二项堆的例子。
据我所知，没有主要的应用程序实际使用 Fibonacci 堆或 Brodal 队列。
Fibonacci 堆最初是为了满足理论需求而不是实际需求而设计的：渐近加速 Dijkstra 的最短路径算法。 Brodal 队列（以及相关的功能数据结构）的设计类似地满足理论保证，具体来说，是为了回答一个长期悬而未决的问题，即是否有可能将斐波那契堆的时间范围与最坏情况保证而不是摊销保证相匹配.从这个意义上说，数据结构不是为了满足实际需要而开发的，而是为了推动我们对算法效率极限的理论理解。据我所知，目前没有任何算法实际上比使用斐波那契堆上的 Brodal 队列更好。
正如其他答案所指出的，隐藏在斐波那契堆或 Brodal 队列中的常数因子非常高。它们需要大量指针连接到许多复杂的链表中，因此，具有绝对糟糕的引用局部性，尤其是与标准二进制堆相比。这意味着在给定缓存效果的情况下，它们在实践中的性能可能会更差，除非您的算法需要大量的减少键操作。在某些情况下会出现这种情况（例如，链接的答案谈到了其中的一些），但将它们视为高度专业化的情况而不是常见的用例。如果您正在处理巨大的图表，则更常见的是使用其他技术来提高效率，例如针对手头的问题使用近似算法、更好的启发式算法或使用基础数据的特定属性的算法。
希望对您有所帮助！
斐波那契堆在实践中是否在任何地方使用？我环顾四周，找到了相关问题的答案（见下文），但实际上没有什么能完全回答这个问题。
- There are good implementations of Fibonacci heaps out there, including in standard libraries such as Boost C++. 这些库包含斐波那契堆的事实表明它们一定在某些地方有用。
- 我们知道斐波那契堆在实践中需要满足某些条件才能更快：“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.”
- 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 很不错 table，比较了不同类型堆的各种操作的时间复杂度。
- 在a question about whether there are any applications of Fibonacci or binomial heaps，回答者只给出了二项堆的例子。
据我所知，没有主要的应用程序实际使用 Fibonacci 堆或 Brodal 队列。
Fibonacci 堆最初是为了满足理论需求而不是实际需求而设计的：渐近加速 Dijkstra 的最短路径算法。 Brodal 队列（以及相关的功能数据结构）的设计类似地满足理论保证，具体来说，是为了回答一个长期悬而未决的问题，即是否有可能将斐波那契堆的时间范围与最坏情况保证而不是摊销保证相匹配.从这个意义上说，数据结构不是为了满足实际需要而开发的，而是为了推动我们对算法效率极限的理论理解。据我所知，目前没有任何算法实际上比使用斐波那契堆上的 Brodal 队列更好。
正如其他答案所指出的，隐藏在斐波那契堆或 Brodal 队列中的常数因子非常高。它们需要大量指针连接到许多复杂的链表中，因此，具有绝对糟糕的引用局部性，尤其是与标准二进制堆相比。这意味着在给定缓存效果的情况下，它们在实践中的性能可能会更差，除非您的算法需要大量的减少键操作。在某些情况下会出现这种情况（例如，链接的答案谈到了其中的一些），但将它们视为高度专业化的情况而不是常见的用例。如果您正在处理巨大的图表，则更常见的是使用其他技术来提高效率，例如针对手头的问题使用近似算法、更好的启发式算法或使用基础数据的特定属性的算法。
希望对您有所帮助！