i'm the student, working on the heaps&queues project during this year's summer of code. i have also been in touch with my mentor about this, but thought, it may be a good idea to hear some comments from other boost devs.
I might as well chime in since I wrote the original project description :) A priority queue is just an adaptor on top of heap (or other "sorted" data structure) -- at least that's my understanding. For example, the std::priority_queue sits on top of a vector (usually) with some special algorithms for push and pop. If you encapsulate that logic as a binary_heap (or maybe flat_heap, if I adopt the Boost.Container notation), then you can effectively decouple the queue from the heap.
i would like to implement the priority queue data as intrusive data structures, which can simply be wrapped to non-intrusive ones. the main reason for this approach is the mutable property.
I think there's a better solution that doesn't require writing intrusive data structures. Not that this is a bad idea, but it's overhead that I'm not looking for in the BGL. Make the user keep user keep track of that information by having push_heap return an iterator and writing an update that takes an iterator, updating the referenced object's position in the heap. If I want, I can track those in an unordered map, if I don't want it, I don't care. I wrote a prototype a couple months ago by modifying the GCC push_heap algorithm. It worked pretty well. The intrusive solution is a good idea also. Maybe both?
the question then would be, whether i should try to introduce it into boost.intrusive, or implement it as a library on its own. boost.intrusive already provides a treap, so it would be quite logical to include heap data structures as well. otoh, having a heap library with both intrusive and non- intrusive data structures, one would have everything in one place. so, i see benefits in both approaches, but would like to hear, what other people think about it ...
I think Intrusive or Container (in the review queue) are probably good targets, depending on what you decide to do. Andrew Sutton andrew.n.sutton@gmail.com