Just how good are Fibonacci heaps?

MIT's 6.854 (Advanced Algorithms) notes on Fibonacci heaps state that Fibonacci heaps are only now coming into practice, as apparently problem sizes are just getting large enough.

Is that so? Are the constant factors hidden behind asymptotic notation too large for Fibonacci heaps compared to binary heaps? Or is it just implementation issues?

To try this theory out, I wrote implementations of a binary heap and a fibonacci heap in Java. Then I wrote a JUnit suite of tests to test correctness. This suite also includes a stress test. The test involved 100k inserts, 300k decrease-key operations, and 100k extract-min operations.

As a baseline metric, I wrote a wrapper around java.util.PriorityQueue. Unfortunately, java.util.PriorityQueue doesn't support the decrease-key operation, so there is some overhead in the wrapper as it takes care of that (and yes, decrease-key *should* take O(log n) or so - I don't use the O(n) remove operation).

So, with 5 runs (a small sample, I know), the time it took for the stress tests are as follows (in seconds):

java.util.PriorityQueue wrapper: 2.453/2.468/2.375/2.281/2.625
Mean: 2.4404 Sample Standard Deviation: 0.1272

Binary Heap: 1.625/1.547/1.500/1.484/1.641
Mean: 1.5594 Sample Standard Deviation: 0.0713

Fibonacci Heap: 1.187/1.141/1.250/1.188/1.172
Mean: 1.1876 Sample Standard Deviation: 0.03972

100k isn't an unrealistic number of elements to use in problems today. Perhaps Fibonacci heaps do have a application in practice - as can be seen from the results above, fibonacci heaps do somewhat better than binary heaps (which themselves beat the baseline minimum) on my stress test. Perhaps the stress test is an unrealistic measure, but I don't think it's that far off.

As an example of its practical usage, you might see my implementation somewhere in Robocraft 2007! (IAP is cool)