斐波那契堆的项目构想 [英] project idea for fibonacci heap

问题描述

我正在学习计算机编程的初级课程，我(和另外3个学生)希望为最终项目实现Fibonacci堆.谁能建议斐波那契堆的一些好的应用?浮华的东西足以成为好的演示材料吗?

I'm in a beginner level computer programming class and I (along with 3 other students) want to implement a Fibonacci heap for a final project. Can anyone suggest some good applications of fibonacci heaps? Something flashy enough to be good presentation material?

推荐答案

(理论上)有许多算法从斐波那契堆的效率中受益，其中最简单的是

There are many algorithms that (theoretically) benefit from the Fibonacci Heap's efficiency, the easiest of which are Dijkstra's Algorithm for Shortest-Path problems, and Prim's Algorithm for Minimum Spanning Trees.

请记住:尽管斐波纳契堆在理论上是最佳的，但在上述两个问题上，它们往往比二进制堆的表现要好.为了使斐波那契堆真正发光，您需要以下两种情况之一: a)昂贵的比较:Fib堆可最大程度地减少组织数据所需的比较次数. b)大多数操作是updateKey/insert/delete.随着斐波那契堆将更新分组在一起，直到下一个extractMin，批处理"越大，它获得的效率就越高.

Do mind: while Fibonacci Heaps are theoretically optimal, they tend to be outperformed by Binary Heaps on the two problems above. 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.

这篇关于斐波那契堆的项目构想的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！