Okay, pending any incredibly prompt responses, this may be the final revision for the project detail section of my proposal, seeing as it's due in about 13 hours now, and I'll be spending several of those sleeping and another couple in class. ===================================== I would like to implement a library which allows a simple, unified concept for a heap/priority queue with a common interface. Through this common interface, I would allow the user to select the specific model to use based on their needs. The standard interface would allow the following functions to be used regardless of the model: - insert - delete - merge - findMin - deleteMin - decreaseKey Furthermore, I would implement the following heap models: - D-ary - Binomial - Fibonacci - Brodal (may be replaced with a different model with similar performance, pending further research) As it stands, the current heap implementations in Boost C++ (specifically in sandbox/libs/pri_queue), take what I think to be slightly the wrong approach. Heaps are conceptually very simple structures, as are their interfaces. By nature, they have a single important element (the minimum), and the rest is treated as a mystery to the outside world. Thus, the issue of iterator access is rather tricky. Many operations can change the structure of the heap so as to invalidate a traversal. These trouble spots would need to be documented. Along the same lines, I feel like a lot of the internal structure can be simplified and memory usage minimized by keeping only pointers to elements. This may seem excessive in the case of simple data types like integers, but I believe it will lead to much simpler memory management, despite the fact that the user will need to handle some of it by themselves. This leads nicely into the use of iterators to simply encapsulate the original data pointers and give them some (arbitrary) order within the structure. This offers a mutability scheme which should perform much better than the reference-based one currently implemented in Boost. A reference-based scheme assumes efficient copy-constructors and does not allow partial updates, both issues which can be circumvented quite gracefully by a pointer-based scheme. All that said, I do believe that the existing d-heap and f-heap implementations can be used as a guide to help me in my development process, in both examining the design decisions along the way and verifying performance. Below are draft interfaces for the base Heap class and the PriorityQueue wrapper class. I've left out some of the tedious bits, such as constructors, in favor of keeping the focus on the functional interface. template <class T, class Compare = std::less<T>> class Heap { public: virtual iterator& insert( T* elem ) = 0; virtual void remove( iterator& elem ) = 0; virtual void update( iterator& elem ) = 0; virtual iterator& findMin() = 0; virtual void removeMin() = 0; virtual void merge( Heap<T,Compare> other ) = 0; virtual bool empty() = 0; virtual int size() = 0; class iterator { public: T& operator* (); T* operator-> (); iterator& operator++(); iterator& operator--(); bool operator== (iterator const& other); bool operator!= (iterator const& other); }; virtual iterator& begin() = 0; virtual iterator& end() = 0; }; template <class T, class Compare = std::less<T>> class PriorityQueue { public: iterator& push( T* elem ); iterator& pop(); void remove( iterator& elem ); void update( iterator& elem ); void merge( PriorityQueue<T,Compare> other ); bool empty(); int size(); class iterator { public: T& operator* (); T* operator-> (); iterator& operator++(); iterator& operator--(); bool operator== (iterator const& other); bool operator!= (iterator const& other); }; virtual iterator& begin() = 0; virtual iterator& end() = 0; private: Heap<T,Compare> data; }; Dan Larkin