Re: [boost] Dietmar Kuehl

From: Dietmar Kuehl (dietmar_kuehl_at_[hidden])
Date: 2002-05-23 18:32:21

Herve Bronnimann wrote:

> Dietmar, Dirk, others: are there any plans to take care of the beta
> priority queues?

Well, yes, there are plans to put them forward at some point but they
are not very concrete. I would welcome if somebody would pick this stuff
up and move it forward.

> Because I was thinking of doing something with it (as a
> "public service" if you will),

I would really appreciate it if somebody would pick up the code. I can
try to help but I cannot guarantee anything with regard to this...

>   1. add allocators in the design, to be able to take advantage of
>      boost::fast_pool_allocator

That's probably reasonable for all the [mostly] node based priority
queues. When I wrote the code I was occupied with the logic and wasn't
comfortable with the details of allocators so I didn't provide this.

>   2. make it STL-compatible by using min-heaps rather than max-heaps
>      (that' actually a piont that we could discuss forever I guess)

I think the literature uses the style I'm currently using, at least the
literature I used to implement it. This is the only reason it is the way
it is: I have no strong feeling about this although the behavior should,
of course, be consistent.

>   3. adding merge operations for heaps (esp. fibonacci heaps)

This should be pretty trivial for Fibonacci heaps. I don't see how this
can be done efficiently for other kinds of heaps, however. Even for
Fibonacci heaps I'm not sure whether it is possible to guarantee a
better complexity than inserting all elements individually (but then,
I have only read about the basic algorithms and I can imagine that it
is possible to merge them more efficiently).

>   4. adding small-rank operations (second_top, third_top?) if it
>      would not surcharge the interface too much

Depending on the kind of heap, this can be done efficiently. Eg. for
Fibonacci heaps I don't think that this can be done efficiently.

>   4. perhaps adding Chazelle's soft heaps (used for approximate sorting
>      and minimum spanning tree)

Can you point to a URL which gives details on this approach? So far I
have implemented (at least partially with respect to radix heaps) all
approaches to heaps I have come across (well, I have omitted to a set
and/or map adaptor) and I would be interested in other approaches, too.

>   5. remove splay heaps and put skew heaps instead (same idea, but
>      specifically for heaps)

Hm, I thought this is what I have implemented... Maybe I goofed things
up and there are better approaches I missed for some reason.

>   6. put an adapter for set and map tree-like data structures (so you'd
>      have the splay heap back, but also red-black heap, avl-heap, etc. by
>      the same token)

A general data structure library. Something between sequence (provided
by the STL) and graphs. That would be nice. Actually, most heaps are
trees and it may be reasonable to provide a tree abstraction(s) and
implement the heaps in terms fo the tree abstraction(s). Then you would
provide different trees and algorithms on trees (eg. rotating,
tree-find, etc.). Also quite interesting...

> If you plan to do anything about it, I can send you concrete ideas and
> proposals along the lines above.

I have no plans to do something with this library in the near future:
Actually, I don't need or use them. Somebody asked for this stuff and I
thought it would be fun to implement it. Then everybody seemed to have
lost interest. I would be glad if someone continues the work. I think it
is a basis to start from.
-- 
<mailto:dietmar_kuehl_at_[hidden]> <http://www.dietmar-kuehl.de/>
Phaidros eaSE - Easy Software Engineering: <http://www.phaidros.com/>