Timeline for What are the disadvantages of Fibonacci Heaps?
Current License: CC BY-SA 4.0
15 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 4, 2023 at 16:17 | comment | added | D.W.♦ | I think it's a little bit misleading to say that delete-min becomes expensive. One delete-min becomes more expensive, but when taken in context of all of the operations, it can still be better than a standard heap, because the speedups outweigh the slowdowns. It's not the case that Fibonacci heap only looks good on the table, or that it was invented only for that purpose - it also leads to better total running time for some algorithms. | |
| May 4, 2023 at 10:02 | comment | added | Qwert Yuiop | @D.W. The difference is that I'm looking at the actual complexity rather than the amortized complexity. Notice that in my analysis, it still comes down to roughly the O(A + B * log(N)) you mentioned. However, in my analysis, part of that O(A) happens not in decrease-key, but in delete-min. This supports my point, that if A/B is the ratio of calls to decrease-key versus delete-min, the higher that ratio, the worse the overall performance of delete-min gets. The fibonacci heap's overall performance doesn't necessarily improve relative to other data structures by increasing the ratio A/B. | |
| May 3, 2023 at 16:41 | comment | added | D.W.♦ | That doesn't look right to me. That looks to me like it contradicts the amortized running times listed in standard textbooks and in Wikipedia. Are you arguing that all of those standard resources are wrong? That seems like it needs some justification (in your answer). I suspect there is a misunderstanding somewhere. Are you familiar with amortized running time analysis? | |
| May 3, 2023 at 8:05 | comment | added | Qwert Yuiop | @D.W. "Therefore, if A≫B, then Fibonacci heaps might be faster than standard heaps." That's exactly the wrong conclusion. For A decrease-key followed by B delete-min, the decrease-key operations add up to workload C0 * A, and the B delete-min operations add up to workload C1 * (A + log(N)) + C2 * (B - 1) * log(N); (that's one expensive delete-min followed by multiple cheap delete-min). It is if delete-min is called reasonably frequently, that it keeps the heap balanced and gets the O(log(N)). If A >> B, then the performance of delete-min gets worse, with roughly O((A / B)) performance. | |
| May 2, 2023 at 17:55 | comment | added | D.W.♦ | 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. | |
| May 2, 2023 at 12:47 | comment | added | Qwert Yuiop | @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)). | |
| May 1, 2023 at 16:09 | comment | added | D.W.♦ | 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. | |
| May 1, 2023 at 7:38 | comment | added | Qwert Yuiop | @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. | |
| Apr 28, 2023 at 18:20 | comment | added | D.W.♦ | 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. | |
| Apr 28, 2023 at 16:10 | review | Late answers | |||
| May 2, 2023 at 9:16 | |||||
| Apr 28, 2023 at 16:00 | history | edited | Qwert Yuiop | CC BY-SA 4.0 |
deleted 3 characters in body
|
| Apr 28, 2023 at 15:59 | history | edited | Qwert Yuiop | CC BY-SA 4.0 |
added 222 characters in body
|
| Apr 28, 2023 at 15:52 | history | edited | Qwert Yuiop | CC BY-SA 4.0 |
added 1 character in body
|
| S Apr 28, 2023 at 15:51 | review | First answers | |||
| May 2, 2023 at 9:12 | |||||
| S Apr 28, 2023 at 15:51 | history | answered | Qwert Yuiop | CC BY-SA 4.0 |