Boost logo

Boost :

Subject: Re: [boost] GSoC 2010: Heaps and Queues
From: Dan Larkin (danielhlarkin_at_[hidden])
Date: 2010-04-08 23:26:46

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 {


       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 {
             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 {


       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 {
             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;


       Heap<T,Compare> data;


Dan Larkin

Boost list run by bdawes at, gregod at, cpdaniel at, john at