Re: [boost] GSoC 2010: Heaps and Queues

Subject: Re: [boost] GSoC 2010: Heaps and Queues
From: Andrew Sutton (andrew.n.sutton_at_[hidden])
Date: 2010-04-06 08:53:07

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

Pointers are used for updating elements after modifying them. Iterators are
just abstract pointers (more or less), so really they play the same role.
They aren't really intended to be used for actual iteration. Besides, you
actually need the iterators for node-based data structures since T* may
point inside a node.

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

This is probably a good evaluation.

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

If you plan to put code in your proposal keep it succinct and address the
code in the text. Basically, leave out the comments :)

Andrew Sutton
andrew.n.sutton_at_[hidden]