Tim Blechmann wrote:
Thomas Klimpel wrote:
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 ...
Oh, you probably assume too much ingenuity from my part. Perhaps it becomes clearer when I use typedefs: typedef value_type* bulk_ptr_type; typedef std::pair<value_type, bulk_ptr_type> heap_value_type; If I store the index into the (arrival time) bulk instead of the pointer, it would read typedef std::size_t bulk_index_type; typedef std::pair<value_type, bulk_index_type> heap_value_type; I have now read (and tried to understand) the similar question from Andrew Sutton with respect to Dijkstra's SP: <http://lists.boost.org/Archives/boost/2011/06/182381.php> (On a slightly unrelated note, I first also used his way to call "update", but that totally killed the performance (and compare count) of fibonacci_heap. I would suggest to remove this form of "update" at least from fibonacci_heap, and require calling "increase" or "decrease" when you have modified the priority "manually".) If I write his approach with typedefs, it would read for my case typedef value_type* bulk_ptr_type; typedef bulk_ptr_type heap_value_type; The other difference is that he stores the returned "handle_type" in a Map, while I store it in a separate bulk (which I called m_tBackpointer) of the same size as the (arrival time) bulk. (A similar bulk is implicitly also present when using TStaticHeap, but it is a part of the heap itself.) So Andrew Sutton's approach to use the mutable interface is not too different from mine, but will probably lead to even worse performance (because a "map" lookup seems to be worse than a "bulk" lookup). On the one hand, your proposed mutable interface seems to be quite "natural" for node based heaps. On the other hand, it looks like there is one more indirection than for a "straightforward" implementation of a "mutable" binary heap, where the heap "knows" the maximum number of different items that it has to manage.
reproduced and fixed the issue with the fibonacci heap ...
Nice. Regards, Thomas