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).
from what i see (taking andrew's example), the problem is the following: struct Vertex { Key k; Queue<Vertex*>::handle_type handle; }; Queue<Vertex*> q; Vertex v; v.handle = q.push(&v); v.key = new_key; q.update(v.handle); ... this is actually the use case, where intrusive mutable heaps would be very handy ...
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.
true ... but this is mainly the point, where the bgl heaps use a propery map ... cheers, tim