hi thomas,
We can see that "fibonacci_heap" has always more than a factor two fewer comparisons than TStaticHeap (a simple text book binary heap implementation used as reference), but is always more than a factor two slower than TStaticHeap. And "fibonacci_heap" seems to be the fastest heap from Boost.Heap in this performance test, while TStaticHeap is still a factor two slower than the tuned TSequentialHeap.
i breefly looked into your heap implementation and it seems to follow a different design than boost.heap ... actually more similar to the implementation of the heaps that are currently used in bgl. this probably explains the performance difference.
I guess the problem here is that I found no way around using "std::pair<value_type, value_type*>" as value_type for the heap, because I need to know the position in the bulk of the point with the smallest arrival time. But Dijkstra algorithm should be no different, I have to know the vertex in the graph with the shortest path.
you mean std::pair<value_type, handle_type> in order to store the handle inside? this may be a hole in the API. at the moment it is possible to convert an iterator to a handle (s_handle_from_iterator), so possibly i should add an handle_type s_handle_from_reference(reference); to all mutable heaps ...
Independent of this, I also have a totally different question. There is a FIXME in line 233 of the test program, and if the following line is commented out, fibonacci_heap shows undefined behavior, ranging from segmentation fault to failing the Sanity Check. Here is the code surrounding the FIXME:
will have a look, what is going wrong here ... tim