Help on using boost relaxed heap

I'm implementing a few graph algorithms at the moment and am wanting a container with the complexity of a fibonacci heap or a relaxed heap (specifically I want at least O(logN) for push and pop and O(1) for reduce_key).

I'm not keen on implementing this myself if at all possible (development and testing overhead and time) and I notice that the boost graph library references a couple of likely looking datastructures in the pending directory. The relaxed heap in relaxed_heap.hpp looks the ticket, but I can't quite work out how to use it. It has the following public functions (precised a little for clarity):

void push(const value_type& x);
value_type& top();
void pop();

Which are clear enough and implement my desired push and pop. Additionally there are:

void update(const value_type& x);
void remove(const value_type& x);

I'm presuming that I can implement a reduce_key using update but I'm not clear how. My particular issue is that I assume the value is copied upon calling push. What I feel I need is a pointer to the copy of the value in the heap so that I can modify it by reference and then call update to have it shuffled back to where it belongs. However such a pointer does not seem to be available?

Anyone with experience of relaxed heaps in general, or boost relaxed heaps in particular willing to pu开发者_Go百科t me out of my misery with an explanation or a nice code snippet?

Thanks,

Alex

---

Alex, if you checkout/download/browse boost library, there's a libs/graph/test directory. One of the tests is relaxed_heap_test.cpp which seems to have coverage of the update member function.

-s-