Re: [boost] GSoC 2010: Heaps and Queues

Subject: Re: [boost] GSoC 2010: Heaps and Queues
From: Daniel Mahler (dmahler_at_[hidden])
Date: 2010-04-06 14:08:18

Hi Dan,

On Tue, Apr 6, 2010 at 5:29 AM, Dan Larkin <danielhlarkin_at_[hidden]> 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
>