Re: [boost] GSoC 2010: Heaps and Queues

Subject: Re: [boost] GSoC 2010: Heaps and Queues
From: Rajendran Thirupugalsamy (rajendran.thirupugal_at_[hidden])
Date: 2010-03-26 13:10:10

Binomial heap and Fibonacci heap can do these operations in constant or
O(log n) amortized.
Basically merge operation can be done in log n.

On Fri, Mar 26, 2010 at 12:10 PM, Andrew Sutton
<andrew.n.sutton_at_[hidden]>wrote:

> > 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]
> _______________________________________________
> Unsubscribe & other changes:
> http://lists.boost.org/mailman/listinfo.cgi/boost
>

-- 
Regards,
Rajendran.T