Hi Dan, On Tue, Apr 6, 2010 at 5:29 AM, Dan Larkin <danielhlarkin@gmail.com> wrote:
Okay. Here's draft revision 1:
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.
On thing to consider is making it an extension of BGL's Buffer concept http://www.boost.org/doc/libs/1_42_0/libs/graph/doc/Buffer.html. I am not sure how widely it is used, but compatibility should never hurt. cheers D
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 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. I feel like the inclusion of iterators is unnecessary, and possibly misguided. This may be a lack of understanding on my part, but I'm frankly confused by how they apply to a heap structure. In any case, I also 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 face that the user will need to handle some of it by themselves. 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 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.
/** * Abstract base class specifying a simple, but fully-featured min-heap * interface. To simplify internal structure, ease the process of making * partial updates to potentially large member elements, and minimize memory * usage, only element pointers are stored, rather than actual data. * * @tparam T Type of elements stored in the heap * @tparam Compare Comparator for type T used for heap-ordering. Defaults to * standard '<' operator. */ template <class T, class Compare = std::less<T>> class Heap {
public:
/** * Inserts a new element into the heap. * * @param elem Pointer to element to insert */ virtual void insert( T* elem ) = 0;
/** * Removes an arbitrary element from the heap and corrects the ordering * if needed. * * @param elem Pointer to element to remove */ virtual void remove( T* elem ) = 0;
/** * Signals the heap that a given element has been updated. The heap may * need to be updated to guarantee a correct ordering. * * @param elem Pointer to element which has been updated */ virtual void update( T* elem ) = 0;
/** * Returns the pointer to the minimum element in the heap. */ virtual T* findMin() = 0;
/** * Removes the minimum element from the heap. */ virtual void removeMin() = 0;
/** * Merges two heaps with the same type of elements. * * @param other Secondary heap to be merged */ virtual void merge( Heap<T,Compare> other ) = 0;
/** * Returns true if no elements remain in the heap, false otherwise. */ virtual bool empty() = 0;
/** * Returns the number of elements in the heap. */ virtual int size() = 0;
};
/** * A flexible priority queue which allows specification of the underlying data * structure upon construction, chosen from the different implementations of * boost::Heap. The default structure is a binary heap. * * @tparam T Type of elements stored in the queue * @tparam Compare Comparator of type T for priority ordering. Defaults to * standard '<' operator. */ template <class T, class Compare = std::less<T>> class PriorityQueue {
public:
/** * Adds a new element to the queue. * * @param elem Pointer to element to push */ void push( T* elem );
/** * Retrieves the pointer to the minimum element in the queue and returns * it, removing the element from the queue afterwards. */ T* pop();
/** * Removes an arbitrary element from the queue and updates the ordering if * needed. * * @param elem Pointer to element to remove */ void remove( T* elem );
/** * Signals the priority queue that a given element has been updated. The * queue may need to be updated to guarantee a correct ordering. * * @param elem Pointer to element which has been updated */ void update( T* elem );
/** * Merges two priority queues with the same type of elements. * * @param other Secondary heap to merge */ void merge( PriorityQueue<T,Compare> other );
/** * Returns true if no elements remain in the queue, false otherwise. */ bool empty();
/** * Returns the number of elements in the heap. */ int size();
private:
//! Heap containing the elements of the priority queue. Responsible for //! maintaining minimum element and providing other I/O functionality. Heap<T,Compare> data;
};
(I apologize if the code looks a bit ugly here, but it should fix itself when copied to a text editor.)
Once again, feedback is welcome. If my interpretation of existing code or the project idea is wrong, please, please point out my stupidity for my sake? Thanks.
Dan Larkin
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost