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?
$\begingroup$
$\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$– plopCommented Jul 10, 2020 at 15:37
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
$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.
answered Jul 10, 2020 at 17:47
$\begingroup$
$\endgroup$
9
It's a bit cheating to call insert and decrease-key O(1), because the implementation is incredibly lazy. The insert and decrease-key increase the entropy of the heap (makes it more messy). Instead of rebalancing immediately (which would make it O(log n)), it procrastinates until delete-min is called, which makes that operation more expensive. It's almost like the Fibonacci heap was invented for the sole purpose of looking good on a time complexity table like that!
So yes, consecutive calls to insert and decrease-key are technically O(1), but it results in mounting debt that you'll have to repay at some point. Since delete-min is the entire point of the priority que, you can't really avoid it. Therefore overall it's not necessarily going to have better performance than alternatives. In fact, it could even be outperformed by non-heap alternatives such as take-min operation on a binary tree.
The O(log n) listed for delete-min is amortized complexity, not worst case complexity. A disadvantage is that due to buildup of entropy/debt as described above, the actual cost of a given call could be as much as O(n). Another disadvantage of the Fibonacci heap is that it uses more memory per element than alternatives like binary heap.
-
$\begingroup$ I think one case where Fibonacci heaps would be better is if you have an algorithm that does lots and lots of decrease-key operations and a relatively small number of delete-min operations. Then your criticism is not valid -- it doesn't result in mounting debt you can't avoid. $\endgroup$– D.W. ♦Commented Apr 28, 2023 at 18:20
-
$\begingroup$ @D.W. In such case you'd have lots of O(1) decrease-key, and a few O(n) delete-min. You pay for the O(1) on insert and decrease-key by making the next call to delete-min more expensive. My criticism is that delete-min is the whole point of the data structure. Nobody is going to get any practical use out of it without calling delete-min. $\endgroup$ Commented May 1, 2023 at 7:38
-
1$\begingroup$ That's not correct. delete-min takes $O(\log n)$ time, not $O(n)$. No one is suggesting there will be applications where delete-min is never called. Rather, I think there might be applications that call decrease-key lots of times, and delete-min a few times. For those applications, the Fibonacci heap might be better, and your criticism is not applicable. $\endgroup$– D.W. ♦Commented May 1, 2023 at 16:09
-
$\begingroup$ @D.W. If you called lots of insert and/or decrease-key, then the next call to delete-min becomes very expensive since it has to rebalance, which could be as much as O(N) in worst case. This is where you pay for the debt of procrastinating on rebalancing. Once balanced, consecutive calls to delete-min take O(log(N)). $\endgroup$ Commented May 2, 2023 at 12:47
-
$\begingroup$ I'm referring to amortized running time. Any sequence of $A$ decrease-key operations and $B$ delete-min operations will take $O(A + B \log n)$ time, with a Fibonacci heap. Compare this to $O(A \log n + B \log n)$ time, for a standard heap. Therefore, if $A \gg B$, then Fibonacci heaps might be faster than standard heaps. In particular, your conclusions are not valid for all applications. See en.wikipedia.org/wiki/Fibonacci_heap. $\endgroup$– D.W. ♦Commented May 2, 2023 at 17:55