fibonacci-heap - 斐波那契堆的项目理念

Question

我正在上初级计算机编程课程，我（与其他 3 名学生一起）想为最终项目实现斐波那契堆。任何人都可以建议斐波那契堆的一些好的应用吗？一些足够华丽的东西可以成为很好的演示材料？

Answer 1

斐波那契堆在一些图算法中用于改善它们的运行时间。这些图形算法可能非常“华丽”，因此您可以展示它们。例如，我相信Dijkstra 的算法有时会使用 Fibonacci Heaps 来实现更好的渐近运行时。

Answer 2

有许多算法（理论上）受益于斐波那契堆的效率，其中最简单的是Dijkstra 的最短路径问题算法和Prim 的最小生成树算法。

请注意：虽然斐波那契堆在理论上是最优的，但在上述两个问题上，它们往往优于二叉堆。要使斐波那契堆真正发挥作用，您需要以下两种情况之一： a) 昂贵的比较：斐波那契堆最大限度地减少了组织数据所需的比较次数。b) 大部分操作是updateKey/insert/delete。由于 Fibonacci Heaps 将更新“分组”在一起，直到下一个 extractMin，“batch”越大，它的效率就越高。