Re: [boost] Heap question

From: T (scream29125_at_[hidden])
Date: 2003-02-16 01:37:57

Hello,

may I know if anyone is maintaining the Boost heap
implementations? The email address of the original
author doesn't seem to exist anymore.

I still have not been able to determine if the
pointers returned by the heap are guaranteed to be
valid. The documentation does not say so. There is a
sample Dijkstra's algorithm written by the original
author but that algorithm involves pushing everything
into the heap at the start and only popping elements
out during the shortest path calculation. This is only
necessary if the graph is a complete graph. In other
cases, the more efficient solution would be to push
elements into the heap only when they are encountered.
The d_heap code seems to indicate that this should
work, but I haven't been able to get it to work. Does
anyone have any pointers as to what other
documentation I could look at?

Thank you.

--- T <scream29125_at_[hidden]> wrote:
> Hello,
> 
> I am implementing an algorithm that requires a heap.
> In my algorithm, I need to do two operations,
> similar
> to that required by Dijkstra's algorithm:
> 
> 1. Use a secondary array to index the nodes of the
> heap. This is so that a node in the heap can be
> found
> in constant time.
> 
> 2. Decrease the key (priority) of a node in the
> heap.
> 
> The Boost heap implementation
> (http://www.boost.org/libs/pri_queue/heap.html)
> supports the decrease-key operation. But reading the
> documentation, I'm not sure if the first requirement
> is satisfied. If I index the nodes using iterators,
> then what I require is for these iterators to be
> valid
> even after the heap is changed, eg after insertion,
> deletion or decreasing the key. Is that the case? 
> 
> Thanks.

__________________________________________________
Do you Yahoo!?
Yahoo! Shopping - Send Flowers for Valentine's Day
http://shopping.yahoo.com