Re: [boost] [gsoc] heaps & queues

Subject: Re: [boost] [gsoc] heaps & queues
From: Andrew Sutton (andrew.n.sutton_at_[hidden])
Date: 2010-04-06 18:44:01

>
>
> I looked at APIs at
> https://svn.boost.org/svn/boost/sandbox/libs/pri_queue/
> The interfaces are quite well designed, but I don't understand one point:
> Why are there function templates used in methods providing mutability
> (for example change_top, change, decrease, increase for the lazy
> Fibonacci heap:
> https://svn.boost.org/svn/boost/sandbox/libs/pri_queue/l_heap.html)? I
> think K stands there for "key", but there's already comparison functor
> (which defaults to std::less) provided, so we don't store key-value
> pairs (with key being the priority), do we?
> Why then K is used?
>

Not sure... Maybe an oversight?

> The second key point I would like to ask about is the implementation.
> Are there any priority queues already implemented in BGL? If so, it
> would be nice for us to stay compatible with interfaces implemented
> already.
>

Not that I'm really aware of. The important ones are in pending.

> * D-ary Heap (with standard - binary - heap as a special case)
> * Fibonacci Heap (btw, I thought, the Fibonacci heap is already lazy -
> maybe there's an discrepancy in the names)
> * Pairing Heap (didn't ever hear about them, but there are lots of
> references in the net)
> * Splay Heap (think it's a gret idea - simple implementaion and quite
> nice performance)
> * Radix Heap (also didn't hear about them, but the intuition is,
> that's a dara structure implementing radix-sort?)
>

This list may be a little long. I would say pick 3 concrete heaps and leave
the others for "if I have time...".

> Speaking about stable priority queues (FIFO- or LIFO- stable) i have
> no fresh ideas for now, but I think it's quite useful, and would be
> happy to implement it.
>

It's better to have an idea than to propose blindly, "I propose to plan P ==
NP!" :) Unfortunately, I don't know of any good references for such data
structures.

> I have read that there are lots of people submitting proposals for the
> project; could any partition of work or time estimation be a part of
> the proposal (because there will surely be at least few of us working
> on the Heaps & Queues)?
>

Unfortunately, not. We'll probably only take one proposal, if any.

Andrew Sutton
andrew.n.sutton_at_[hidden]