Re: [boost] GSoC 2010: Heaps and Queues

Subject: Re: [boost] GSoC 2010: Heaps and Queues
From: Dan Larkin (danielhlarkin_at_[hidden])
Date: 2010-04-05 23:29:36

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.

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