STL for Fibonacci Heap?

Question

where is the Fibonacci Heap in STL ? and if STL do not implement Fibonacci Heap what is the best practice to implement it using existing algorithms and containers in STL ?

Solution 1

boost has an implementation of it. Hope that helps. There doesn't seem to be one in the STL. Here's an example:

 for(int n=0;n<40;++n){
    std::cout<<"F("<<n<<")="<<fibonacci(n)<<std::endl;
  }

Solution 2

Even though it is not stated explicitly as a Fibonacci heap, the STL implements a priority_queue which has the same complexity and the same api and behavior as a Fibonacci heap (and may actually be a Fibonacci heap in disguise)

https://en.cppreference.com/w/cpp/container/priority_queue

Comments

[mix]

std::priority_queue is container adaptor which means that it takes another container (like std::vector) and provides new operations using that container in the background. It requires its container to provide random access iterator which means that it uses binary heap in the background (theoreticaly it could use other heap implementation based on arrays). Bianary heap and Fibonacci heap don't have the same complexities. STL queue also has limited api compared to i.e. boost Fibonacci heap.