Re: Bug fixes and interface changes for priority queues

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