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-03-26 12:10:40

> I'm another potential student throwing my hat in the ring for the heap
> project.
>

Hi Dan,

Sorry I've been slow responding. I'm having trouble keeping track of which
GSoC email I've responded to :)

> The way I see it, the current heap implementations in boost/pending are
> rather fractured.  They just have simple push/pop interfaces with no
> mutability (well, there's mutable_heap.hpp, but that's separate and not
> fleshed out).
>

That's a fairly accurate description of the state of things. You should also
look at the C++ Standard heap algorithms and priority queue. You might want
to consider what how you might change those to support mutability in
standard heaps.

I know that a stable priority queue was mentioned in earlier discussion, but
> I'm not sure what to do about that just yet.
>

In general a priority queue can essentially be thought of as a queue adaptor
for an (partially?) ordered data structure. Stability is a property of the
ordering of elements in the underlying data structure. Such that two
equivalent objects in the queue will be popped in the reverse order of their
insertion. Or was it the same order? You could probably make arguments for
either or as long as its deterministic.

I guess that's basically how I see the problem so far.  Please let me know
> what you think, or what other sort of information/planning/etc. you would
> like to hear from me prior to my proposal/draft.
>

Draft proposals are welcome. It's easier to give feedback than to suggest
ideas :)

Andrew Sutton
andrew.n.sutton_at_[hidden]