hi all, since the heaps/queues project is likely to be used by multiple people, i think it may be a good idea to share some ideas on the list ... for now, i have been implementing a (non-intrusive) d-ary heap, which was very useful to do some prototyping of the actual interface. all data structures support the following template arguments: typename T // value type bool stable // stability class Cmp // compare object class Alloc // allocator for internal data structures the interface matches the forward container requirement, except that it does not support iterators (only const_iterators) and container comparison. at the moment, i distinguish between immutable and mutable heaps. the interface for immutable heaps would look like this: class immutable_heap { public: // priority queue support value_type const & top(void) const; void push(value_type const & v); void pop(void); // merge support void merge (immutable_heap const & rhs); void merge_and_clear (immutable_heap & rhs); // moves all elements from rhs to *this }; for mutable heaps, i have been using a `handle' to refer to specific elements: class mutable_heap { public: typedef handle_type; // priority queue support value_type const & top(void) const; handle_type push(value_type const & v); void pop(void); // update via function void update(handle_type const & node, value_type const & v); void increase(handle_type const & node, value_type const & v); void decrease(handle_type const & node, value_type const & v); // force update after element has been changed via the handle void update(handle_type const & node); void increase(handle_type const & node); void decrease(handle_type const & node); // merge support void merge (mutable_heap const & rhs); void merge_and_clear (mutable_heap & rhs); }; the forced update api is rather dangerous, since the heap would enter an undefined state, of the node is changed, but the heap is not updated. otoh, it would help to update values using a different api than the assignment operator. also, i am unsure, whether by default the heaps should be min-heaps (like in most textbooks on data structures) or max-heaps (like std::priority_queue). so i'd be curious, what people think about it ... the code is available from my public git repository. i would be curious to hear some thoughts! http://tim.klingt.org/git?p=boost_heap.git cheers, tim -- tim@klingt.org http://tim.klingt.org A year ago, six months ago, I thought that I was an artist. I no longer think about it, I am. Henry Miller