The heap's intention is to be used for Dijkstra's algorithm, where the distances only decrease. You might want to look at Boost.Heap as well, since d_ary_heap_indirect is meant mostly for internal BGL use.
The reason I was using d_ary_heap_indirect was for the "indirect" part. I want to store objects (vertices) in the priority queue, but prioritize them based on values in an external map (the PriorityMapType in my examples). From the documentation it doesn't look like Boost.Heap can do that (http://www.boost.org/doc/libs/1_51_0/doc/html/heap/concepts.html#heap.concep...) - am I missing it? (Also, Boost.Heap seems to have exactly the interface I was suggesting of an increase(), decrease(), and update() if you're not sure which of the two former functions to use.)
If that doesn't work, I can try putting in the update function you want as long as it always correctly preserves the heap invariants.
I don't know how we would prove that it always maintains the invariants, but it seems to make sense, right? It just (currently) goes up the queue, swapping if it is out of order, then goes down the queue (new addition), swapping if it is out of order. If the first pass (_up() ) does find a reason to swap, then the down() pass would just do nothing (as the swapped item is guaranteed to be larger than any of the ones below the position of the item to update). If the up() pass does nothing, then the down() pass would work as normal. David