STL for Fibonacci Heap??

Discussion in 'C++' started by Lance, Dec 1, 2003.

  1. Lance

    Lance Guest

    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
     
    Lance, Dec 1, 2003
    #1
    1. Advertising

  2. Lance

    Dave Guest

    "Lance" <> wrote in message
    news:...
    > 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...
     
    Dave, Dec 1, 2003
    #2
    1. Advertising

  3. Lance

    Chris Theis Guest

    "Dave" <> wrote in message
    news:...
    >
    > "Lance" <> wrote in message
    > news:...
    > > 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
     
    Chris Theis, Dec 1, 2003
    #3
  4. Lance

    Dave O'Hearn Guest

    "Lance" <> 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
     
    Dave O'Hearn, Dec 1, 2003
    #4
  5. "Lance" <> 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:> <http://www.dietmar-kuehl.de/>
    Phaidros eaSE - Easy Software Engineering: <http://www.phaidros.com/>
     
    Dietmar Kuehl, Dec 1, 2003
    #5
  6. (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:> <http://www.dietmar-kuehl.de/>
    Phaidros eaSE - Easy Software Engineering: <http://www.phaidros.com/>
     
    Dietmar Kuehl, Dec 2, 2003
    #6
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Sachin Garg
    Replies:
    10
    Views:
    769
    Buster
    Sep 20, 2004
  2. Replies:
    4
    Views:
    2,846
    red floyd
    Sep 21, 2006
  3. Michal Slocinski

    Heap dump file size vs heap size

    Michal Slocinski, Mar 25, 2008, in forum: Java
    Replies:
    1
    Views:
    752
    GArlington
    Mar 25, 2008
  4. viki
    Replies:
    6
    Views:
    584
    Erik Wikström
    Jun 28, 2008
  5. Raymond Schanks
    Replies:
    0
    Views:
    557
    Raymond Schanks
    Apr 11, 2010
Loading...

Share This Page