STL for Fibonacci Heap??

[Lance]

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

[Dave]

"Lance" <La***@nospam.com> wrote in message
news:2c******************************@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...

[Chris Theis]

"Dave" <be***********@yahoo.com> wrote in message
news:vs************@news.supernews.com...

"Lance" <La***@nospam.com> wrote in message
news:2c******************************@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

[Dave O'Hearn]

"Lance" <La***@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

[Dietmar Kuehl]

"Lance" <La***@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:di***********@yahoo.com> <http://www.dietmar-kuehl.de/>
Phaidros eaSE - Easy Software Engineering: <http://www.phaidros.com/>

[Dietmar Kuehl]

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/>