[boost] [gsoc] heaps & queues

Subject: [boost] [gsoc] heaps & queues
From: Cezary Bartoszuk (cbart_at_[hidden])
Date: 2010-04-06 16:30:20

Hi,

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?

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.

Besides few doubts listed above I would like to propose implementing
at least pri queues listed in
https://svn.boost.org/svn/boost/sandbox/libs/pri_queue/, so:

* 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?)

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.

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)?

Best regards,
Cezary Bartoszuk

P.S.

As I read threads about heaps & queues, I think also that the
interfaces are a little bit too complicated. Quite good idea is
implementing methods push, min, pop, decrease_key. Personally I don't
see any algorithms using both decrease_key and increase_key. Usually
there is intention of pushing priority "to the front" rather than "to
the back". And there is also thing with iterators: I haven't seen any
implementation iterating through pri_queue.
So are interfaces based on push, min, pop, decrease_key accurate?