3
$\begingroup$

A Fibonacci heap is a data structure for priority queue / heap operations. It seems to have the best complexity for all operations:

enter image description here

Since it has the best performance, why not use it everywhere? What are the disadvantages of it?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ Those are asymptotic orders of growth of the number of operations (some of them of the expected value of the number of steps) in terms of the size of the input. They are not exact number of operations, or even estimations that give information for all values of $n$. From that information alone you cannot deduce that for a particular value of $n$ or for a fixed collection of values of $n$ one is faster than the other. $\endgroup$
    – plop
    Jul 10, 2020 at 15:37

1 Answer 1

Reset to default
6
$\begingroup$

$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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.