1

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?

Tony
  • 173
  • 1
  • 6

2 Answers2

1

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.

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.

Gaminic
  • 581
  • 3
  • 9
1

Fibonacci heaps are used in some graph algorithms to improve their runtime. These graph algorithms might be pretty "flashy", so you could showcase those. For example, I believe Dijkstra's algorithm sometimes uses Fibonacci Heaps to achieve better asymptotic runtime.

Oleksi
  • 12,947
  • 4
  • 56
  • 80