- **C++**
(*http://www.velocityreviews.com/forums/f39-c.html*)

- - **STL for Fibonacci Heap??**
(*http://www.velocityreviews.com/forums/t279637-stl-for-fibonacci-heap.html*)

STL for Fibonacci Heap??What is the correct STL libraries to implement in order to have a Fibonacci
Heap created? I am creating an algorithm which would use a Fibonacci Heap. Thanks, Lance |

Re: STL for Fibonacci Heap??"Lance" <Lance@nospam.com> wrote in message news:2c4782b221172867247929a90a8a1056@news.teranew s.com... > What is the correct STL libraries to implement in order to have a Fibonacci > Heap created? > > I am creating an algorithm which would use a Fibonacci Heap. > > > > Thanks, > > Lance > > I can't think of any exceptions to the statement that the C++ Standard does not mandate a particular implementation for any of the STL containers except for stating that the elements in a vector<> must be stored contiguously (what it *does* mandate is performance requirements). I'm sure others will correct me if I'm wrong about this, but I think the only way you're going to get a Fibonacci heap for sure in Standard C++ is if you implement it yourself... |

Re: STL for Fibonacci Heap??"Dave" <better_cs_now@yahoo.com> wrote in message news:vsldaga54sdp4e@news.supernews.com... > > "Lance" <Lance@nospam.com> wrote in message > news:2c4782b221172867247929a90a8a1056@news.teranew s.com... > > What is the correct STL libraries to implement in order to have a > Fibonacci > > Heap created? > > > > I am creating an algorithm which would use a Fibonacci Heap. > > There is no such thing as a correct STL library - in principle the former STL has been included and is now the C++ standard library shipped with every recent compiler. If you mean that there is such a thing as a Fibonacci Heap included in the C++ library I'll have to disappoint you. It's up to you to do the implementation. [SNIP] > > I can't think of any exceptions to the statement that the C++ Standard does > not mandate a particular implementation for any of the STL containers except > for stating that the elements in a vector<> must be stored contiguously > (what it *does* mandate is performance requirements). [SNIP] This statement is not entirely true in this form. The standard does not make statements about the details of the container implementations but there are further requirements specified that go beyond performance. For example the iterator access is specified for the containers, some points regarding the requirements on the contained types and further requirement regarding e.g. associative containers are given (I think there is no point in listing this stuff here). Regards Chris |

Re: STL for Fibonacci Heap??"Lance" <Lance@nospam.com> wrote:
> What is the correct STL libraries to implement in order to have a Fibonacci > Heap created? > > I am creating an algorithm which would use a Fibonacci Heap. The standard library has some heap algorithms, and a priority_queue adapter, but they don't mandate the interal structure of the heap, just a few operations. IIRC, "union" operations are not amoung these, so it is probably going to be a binary heap in any implementation. FWIW, I have never seen anyone use a Fibonacci Heap... not even in a homework. Supposedly, there is a Perl library that implements them, but that is the only one I've ever heard of. -- Dave O'Hearn |

Re: STL for Fibonacci Heap??"Lance" <Lance@nospam.com> wrote:
> What is the correct STL libraries to implement in order to have a Fibonacci > Heap created? > > I am creating an algorithm which would use a Fibonacci Heap. I don't really understand your question: as is, it does not make much sense... My guess is that you want to know where to get a library from which includes a Fibonacci heap and integrates well with the standard C++ library. If this is indeed your question, you can download <http://www.dietmar-kuehl.de/cxxrt/heaps.tar.gz>. This archive contains a bunch of different heap implementations with a common interfaces. Several of the heaps support changes of the "key". -- <mailto:dietmar_kuehl@yahoo.com> <http://www.dietmar-kuehl.de/> Phaidros eaSE - Easy Software Engineering: <http://www.phaidros.com/> |

Re: STL for Fibonacci Heap??daveoh77@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:dietmar_kuehl@yahoo.com> <http://www.dietmar-kuehl.de/> Phaidros eaSE - Easy Software Engineering: <http://www.phaidros.com/> |

All times are GMT. The time now is 05:04 PM. |

Powered by vBulletin®. Copyright ©2000 - 2014, vBulletin Solutions, Inc.

SEO by vBSEO ©2010, Crawlability, Inc.