patternMinor
What are the disadvantages of Fibonacci Heaps?
Viewed 0 times
thewhatfibonacciaredisadvantagesheaps
Problem
A Fibonacci heap is a data structure for priority queue / heap operations. It seems to have the best complexity for all operations:
Since it has the best performance, why not use it everywhere?
What are the disadvantages of it?
Since it has the best performance, why not use it everywhere?
What are the disadvantages of it?
Solution
$O(1)$ merely means that no matter how large your heap grows, the operation will always take roughly the same time to execute. It doesn't mean "the fastest".
Wikipedia article you linked has section named "Practical considerations":
Fibonacci heaps have a reputation for being slow in practice due to
large memory consumption per node and high constant factors on all
operations. Recent experimental results suggest that Fibonacci heaps
are more efficient in practice than most of its later derivatives,
including quake heaps, violation heaps, strict Fibonacci heaps, rank
pairing heaps, but less efficient than either pairing heaps or
array-based heaps.
Wikipedia article you linked has section named "Practical considerations":
Fibonacci heaps have a reputation for being slow in practice due to
large memory consumption per node and high constant factors on all
operations. Recent experimental results suggest that Fibonacci heaps
are more efficient in practice than most of its later derivatives,
including quake heaps, violation heaps, strict Fibonacci heaps, rank
pairing heaps, but less efficient than either pairing heaps or
array-based heaps.
Context
StackExchange Computer Science Q#128226, answer score: 6
Revisions (0)
No revisions yet.