160

Has anyone of you ever implemented a Fibonacci-Heap? I did so a few years back, but it was several orders of magnitude slower than using array-based BinHeaps.

Back then, I thought of it as a valuable lesson in how research is not always as good as it claims to be. However, a lot of research papers claim the running times of their algorithms based on using a Fibonacci-Heap.

Did you ever manage to produce an efficient implementation? Or did you work with data-sets so large that the Fibonacci-Heap was more efficient? If so, some details would be appreciated.

Improve this question
6
  • 27
    Haven't you learned these algorithm dudes always hide their huge constants behind their large big oh?! :) It seems in practice, most of the time, that "n" thing never gets even close to the "n0"! Commented Feb 2, 2009 at 20:54
  • I know - now. I implemented it when I first got my copy of "Introduction to Algorithms". Also, I didn't pick Tarjan for someone who would invent a useless data-structure, because his Splay-Trees are actually quite cool. Commented Feb 2, 2009 at 21:05
  • mdm: Of course it's not useless, but just like insertion sort which beats quicksort in small data sets, binary heaps might work better due to smaller constants. Commented Feb 2, 2009 at 21:36
  • 1
    Actually, the program I needed the heap for was finding Steiner-Trees for routing in VLSI-chips, so the data sets were not exactly small. But nowadays (except for simple stuff like sorting) I would always use the simpler algorithm until it "breaks" on the data-set. Commented Feb 2, 2009 at 21:46
  • 1
    My answer to this is actually "yes". (Well, my coauthor on a paper did.) I don't have the code right now, so I'll get more info before I actually respond. Looking at our graphs, however, I note that F heaps make less comparisons than b heaps. Were you using something where comparison was cheap? Commented Feb 3, 2009 at 15:09

6 Answers 6

Reset to default
148

The Boost C++ libraries include an implementation of Fibonacci heaps in boost/pending/fibonacci_heap.hpp. This file has apparently been in pending/ for years and by my projections will never be accepted. Also, there have been bugs in that implementation, which were fixed by my acquaintance and all-around cool guy Aaron Windsor. Unfortunately, most of the versions of that file that I could find online (and the one in Ubuntu's libboost-dev package) still had the bugs; I had to pull a clean version from the Subversion repository.

Since version 1.49 Boost C++ libraries added a lot of new heaps structs including fibonacci heap.

I was able to compile dijkstra_heap_performance.cpp against a modified version of dijkstra_shortest_paths.hpp to compare Fibonacci heaps and binary heaps. (In the line typedef relaxed_heap<Vertex, IndirectCmp, IndexMap> MutableQueue, change relaxed to fibonacci.) I first forgot to compile with optimizations, in which case Fibonacci and binary heaps perform about the same, with Fibonacci heaps usually outperforming by an insignificant amount. After I compiled with very strong optimizations, binary heaps got an enormous boost. In my tests, Fibonacci heaps only outperformed binary heaps when the graph was incredibly large and dense, e.g.:

Generating graph...10000 vertices, 20000000 edges. Running Dijkstra's with binary heap...1.46 seconds. Running Dijkstra's with Fibonacci heap...1.31 seconds. Speedup = 1.1145.

As far as I understand, this touches at the fundamental differences between Fibonacci heaps and binary heaps. The only real theoretical difference between the two data structures is that Fibonacci heaps support decrease-key in (amortized) constant time. On the other hand, binary heaps get a great deal of performance from their implementation as an array; using an explicit pointer structure means Fibonacci heaps suffer a huge performance hit.

Therefore, to benefit from Fibonacci heaps in practice, you have to use them in an application where decrease_keys are incredibly frequent. In terms of Dijkstra, this means that the underlying graph is dense. Some applications could be intrinsically decrease_key-intense; I wanted to try the Nagomochi-Ibaraki minimum-cut algorithm because apparently it generates lots of decrease_keys, but it was too much effort to get a timing comparison working.

Warning: I may have done something wrong. You may wish to try reproducing these results yourself.

Theoretical note: The improved performance of Fibonacci heaps on decrease_key is important for theoretical applications, such as Dijkstra's runtime. Fibonacci heaps also outperform binary heaps on insertion and merging (both amortized constant-time for Fibonacci heaps). Insertion is essentially irrelevant, because it doesn't affect Dijkstra's runtime, and it's fairly easy to modify binary heaps to also have insert in amortized constant time. Merge in constant time is fantastic, but not relevant to this application.

Personal note: A friend of mine and I once wrote a paper explaining a new priority queue, which attempted to replicate the (theoretical) running time of Fibonacci heaps without their complexity. The paper was never published, but my coauthor did implement binary heaps, Fibonacci heaps, and our own priority queue to compare the data structures. The graphs of the experimental results indicate that Fibonacci heaps slightly out-performed binary heaps in terms of total comparisons, suggesting that Fibonacci heaps would perform better in a situation where comparison cost exceeds overhead. Unfortunately, I do not have the code available, and presumably in your situation comparison is cheap, so these comments are relevant but not directly applicable.

Incidentally, I highly recommend trying to match the runtime of Fibonacci heaps with your own data structure. I found that I simply reinvented Fibonacci heaps myself. Before I thought that all of the complexities of Fibonacci heaps were some random ideas, but afterward I realized that they were all natural and fairly forced.

Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

Thanks! This question had been sitting on my mind for a long time. I actually implemented Dijkstra's using Fibonacci-Heaps before I attempted Steiner-Trees. However, it seems that my graphs where much less dense than in your example. They had millions of nodes, but an average degree of only 5-6.
Fib Heap performance is predictable via the sequence of operations. I've written an Heap-heavy algorithm that ended up faster with the Fib Heap (vs. Bin Heap). The trick was batching the work. Regardless of the frequency of any operation, the difference lies here: DecreaseKey - ExtractMin - DecreaseKey - ExtractMin versus DecreaseKey - DecreaseKey - ExtractMin - ExtractMin (contd. below)
The latter will be roughly twice as fast, because the 2nd ExtractMin is nearly free. Our algorithm extracts a batch of Min elements of which many are discarded; a waste on a Bin Heap, but better on a Fib Heap. Sadly this isn't clearly reflected in the time complexity people provide when talking about Heap-based algorithms. With Amortized bounds, the total complexity isn't simply # operations * complexity of operation.
Any chance of also trying pairing heaps and/or relaxed heaps?
I'm not sure why your results appeared so close, I used STL priority_queue vs self-implemented fibonacci heap and the binary heap was behind by a large margin in my tests.
37

Knuth did a comparison between fibonacci heap and binary heaps for minimum spanning trees back in 1993 for his book Stanford Graphbase. He found fibonacci to be 30 to 60 precent slower than binary heaps at the graph sizes he was testing, 128 vertices at different densities.

The source code is in C (or rather CWEB which is a cross between C, math and TeX) in the section MILES_SPAN.

Improve this answer

Comments

1

Disclaimer

I know results are quite similar and "looks like running time is totally dominated by something other than the heap" (@Alpedar). But I couldn't find anything evidence of that in the code. The code it's open, so if you can find anything that can affect the result of the test, please tell me.

Maybe I did something wrong, but i wrote a test, based on A.Rex anwser comparing:

  • Fibonacci-Heap
  • D-Ary-heap (4)
  • Binary-Heap
  • Relaxed-Heap

The execution times (for complete graphs only) for all heaps were very close. The test were made for complete graphs with 1000,2000,3000,4000,5000,6000,7000 and 8000 vertices. For each test 50 random graphs were generated and the output is the average time of each heap:

Sorry about the output, it's not very verbose because i needed it to build some charts from text files.

Here are the results (in seconds):

heap result table

Improve this answer

6 Comments

How much edges are there in each case? And what algorithm are you running exactly? Your results don't make sense if we don't know what we are dealing with.
As i sad , all graph are completes , so you can calculate the number of edges for each case. What you mean, "are you running exactly". They are in the head of the tables.
This looks like running time is totally dominated by something other than the heap (it could be generating of graph or some IO). Those almost exactly same results are unbelievable.
Well maybe the time os dominated by something else, but i am sure that isn't the IO or the generation of the graphs. Anyway the source code is available and i will be very glad if someone find an error and correct the mesure.
Those tests seem to be measuring something entirely different. Could you comment on the test you ran? Remember that the Shortest Path Problem on a complete graph is O(1) if distances are Geometric/Euclidian.
|
0

I also did a small experiment with Fibonacci heap. Here is the link for the details: Experimenting-with-dijkstras-algorithm. I just googled the terms "Fibonacci heap java" and tried a few existing open-source implementation of the Fibonacci heap. It seems that some of them have some performance issue, but there are some which is quite good. At least, they are beating the naive and the binary heap PQ performance in my test. Maybe they can help to implement the efficient one.

Improve this answer

Comments

0

There's a pretty comprehensive answer, plus a tested C++ implementation of Dijkstra's algorithm with Fibonacci heaps here

Improve this answer

1 Comment

To expand on my answer above, the following paper that I wrote uses an efficient Fibonacci heap implementation with Dijkstra's algorithm. It generally finds that it is as about the same speed as using heaps and binary trees, depending on the input graph's density. There's also a link to the C++ source code in the paper. arxiv.org/abs/2303.10034
0

The Fibonacci heap is actually just a binomial heap with corruptions, like the cut, which discards sorting effort and burdens you with tracking the marked nodes. I got best time using a modified binomial heap, as it has best locality of reference for cache, dynamic RAM, and page fault advantages. And unlike an array Priority Queue, one does not need to know the problem size or need to expand the array to fit a problem grown too large! The binomial heap merges just as easily as the Fibonacci heap, by combining root tree lists, merging any same-rank trees, O(log N) of the smaller heap.

  1. I defer min discernment until min peek or pop, so insert is not burdened. Since many problems end by discarding the rest of the heap, insert speed is of tantamount importance. Insert is O(1) on average even with my aggressive and sorted merge.
  2. I aggressively merge on input, keeping the root forest as a simple rank ascending sorted forward linked list.
  3. I keep the node small; my node has just 4 elements: templated/generic value, char/byte rank (rank is a binary power, so 2^127 is big enough), pointer/references next and child. My class has just a root pointer and methods.
  4. On peek or pop min, I merge the entire root forest into one tree by assigning any lower rank nodes the rank of the next higher rank node and merging them. This pushes many trees deep down inside the final tree, reducing future root width, while doing real sorting for future profit. Just locating the min does no sorting for the future. Once all root trees are merged, the min is in the only root node.

Attached find a c++ include file for a min heap, demanding operator< from templated types, and a JAVA file demanding implement Comparable from generic classes. C++ include file of Min Heap Class JAVA BMH class source Test of JAVA BMH source Comparable test of JAVA PriorityQueue

I left out the update and delete not min, as most application need neither of these, and they can have speed and space impact. They is easy to add. A more involved class could support them, when users need them and decide to take any speed and space hit. There seems to be some ambiguity on how the node to be updated/deleted is identified: by search (O(N)) or by user stored reference (pointer or object reference). Update is a delete and then reinsert the updated node, after moving any children in place of the deleted node, which is in either the root if deleted from root or in the child or next list of the prior/parent node, thus preserving the sort effort of their position within the tree. If the children are going into the root list, this involves normal merging. Update/delete by pointer/reference (without a brute force search) forces you to add to the node space and processing burden, adding and maintaining a prior/parent pointer in every node, so the not-min node can be deleted and any of its children added in its place. With a brute force search, you can determine the prior/parent on the fly. The current JAVA PriorityQueue seems to only offer a brute force search delete, no update.

Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.