Re: [Boost-users] BGL: d_ary_heap_indirect duplicated values

Subject: Re: [Boost-users] BGL: d_ary_heap_indirect duplicated values
From: David Doria (daviddoria_at_[hidden])
Date: 2012-09-05 12:56:29

> 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.concepts.mutability)
- 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