I looked over and tried your code; there are two issues that I see:
1. The index_in_heap_map is initialized to 0, rather than (size_t)(-1) (the 4294967295 you are seeing after vertices are popped). It looks like that isn't a problem when an unconditional push is used to add to the queue, but push_or_update does check whether the element is already in the queue.
Where do you see this being initialized to zero? (i.e. where should I changed it to be initialized to -1?). I thought that this map was being set explicitly in the push() function anyway (so why does the initialization matter)?
2. It looks like copying d_ary_heap_indirect objects doesn't work correctly (it should probably be a shallow copy, while here it is trying to do a mix of both). Thus, your output routine is removing elements from a copy of the heap data (since the heap structure itself is deep-copied) while marking them "not present" in the original index_in_heap_map (since that is shallow-copied). I'll just make it noncopyable for now, and it will likely stay that way unless someone has a compelling need for something else.
Ah, I see that now. How else would I inspect the current ordering? I guess just pop them all off into another container and then push them all back in? David