da******@pobox.com (Dave O'Hearn) wrote:

FWIW, I have never seen anyone use a Fibonacci Heap... not even in a

homework.

First off, I have seen it used, eg. by myself in shortest path algorithms:

it is the canonical data structure for things like Dijkstra's algorithm

although there are approaches to avoid it (although at the cost of a

higher complexity).

In general, there are two reasons why people don't use Fibonacci Heaps:

1. The data structure is assumed to be relatively hard to implement and

there are alternatives which are assumed to be easier to implement.

2. The theoretical advantage of Fibonacci Heaps is assumed to pay off

only for very large data sets due to inherently bigger constants.

Both assumptions are wrong. The second is, however, not that unreasonable:

it takes quite some tuning the implementation to make them reasonably fast

for reasonably sized data sets. ... and, indeed, the pay off (O(n) rather

than O(n lg n) complexity for some operations) kicks in only with fairly

large data sets.

BTW, you can download an implementation of several different heaps,

including a Fibonacci Heap implementation, from

<http://www.dietmar-kuehl.de/cxxrt/heaps.tar.gz>.

--

<mailto:di***********@yahoo.com> <http://www.dietmar-kuehl.de/>

Phaidros eaSE - Easy Software Engineering: <http://www.phaidros.com/>