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?
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@gmail.com
participants (2)
-
Andrew Sutton -
Cezary Bartoszuk