From: brianjparker_at_[hidden]
Date: 2001-10-28 19:33:40
--- In boost_at_y..., Jeremy Siek <jsiek_at_c...> wrote:
> Hi Brian,
>
> I'm glad to hear someone is working on this. Priority queues are
indeed
> important. I'll take a look at you stuff soon.
>
> May I also suggest that you take a look at
> boost/pending/mutable_queue.hpp. That's the queue currently used in
the
> graph library.
Hi Jeremy,
I have had a quick look at boost/pending/mutable_queue.hpp and I
thought I would give my initial impressions. I will actually try it
out at a later date.
(1) The first issue is that it would not be usable in my current
algorithm as it has no erase() member which is essential for many
uses of modifiable heaps (the implementation using a vector would
probably (??) make this difficult to implement- a node-based
implementation is required).
(2) I don't think I like the need for a functor for each value type
to generate a unique ID to implement update(). It seems like a kludge
and burden on the user, and I don't see how it would handle repeated
values in the queue. Trivial iterators (as I call them, or "pointers"
as Dietmar originally called them, or "items" as the LEDA library
calls them) are are more direct approach. In any case trivial
iterators are needed in my algorithm to be able to dereference the
pointed-to element after insertion. To allow this using your approach
it seems you would need to expose the node lookup machinery to the
user.
(3) Limiting the implementation to a random access container seems a
limitation. Could a Fibonacci heap be used in this implemntation
without compromising its performance guarantees?
(4) There is no meld operation provided.
As I said, these are just my initial impressions- my apologies if I
have misinterpreted some aspects of your design.
Further comments to follow,
Brian Parker