Re: [boost] status of fibonnaci_heap and mutable_queue

From: Fernando Cacciola (fernando_cacciola_at_[hidden])
Date: 2006-04-06 17:10:42

Douglas Gregor wrote:
> On Apr 6, 2006, at 8:46 PM, Fernando Cacciola wrote:
>
>> I'm in need of a mutable priority queue.
>
> If it fits what you need, there is the relaxed_heap data structure.
> However, it has a rather minimal interface that's meant for the graph
> library.
>

All I need is a priority queue with an update() operation (which of course 
can potentially replace the top element), so yes, if I understood the 
interface correctly, this is exactly what I need!!

It's also under pending, but I guess this one is actually used in the BGL so 
is trustworthy, right?

BTW: a related question that it think you can answer:

This DS needs an index map from the IndexedType to an integral index in the 
range [0,n].

But my algorithm will run over non-indexed types which might not even be 
stored in a radom access container.

If I understand the propery maps library correctly, I'll need to create a 
map, or hash_map, associating each and every possible value with an int, and 
wrap that into an associative_property_map<> to input into the relaxed_heap 
DS.

Is that right?

TIA

Fernando Caccio.a