Re: [boost] [gsoc] heaps

Subject: Re: [boost] [gsoc] heaps
From: Raymond Wan (r.wan_at_[hidden])
Date: 2010-06-11 10:07:19

Hi David,

On Fri, Jun 11, 2010 at 22:53, David Abrahams <dave_at_[hidden]> wrote:
> At Fri, 11 Jun 2010 22:42:10 +0900,
> Raymond Wan wrote:
>>
>> On Fri, Jun 11, 2010 at 21:48, Tim Blechmann <tim_at_[hidden]> wrote:
>> > also, i am unsure, whether by default the heaps should be
>> min-heaps (like in > most textbooks on data structures) or max-heaps
>> (like std::priority_queue). Â > so i'd be curious, what people think
>> about it ...
>
> Compatibility with similar structures from std is a good place to
> start. Â It would be annoying to replace an std::priority_queue
> with one of yours and discover that I needed to invert the comparison
> operator.

True.  But one can also say that a heap (max-heap) and a priority
queue are two separate things -- the latter is kind of an abstraction?
 A priority queue is just a queue of items with an assigned priority;
no one says that it has to be implemented using a heap.  Of course, in
practice, most books and instructors use a heap only because it is one
of the easiest ways to do it.  I suppose a priority queue can be
implemented less efficiently using a binary search tree and still be
called a priority queue?

That is, maybe a max-heap shouldn't be interchangeable with a priority
queue?  Or, that a heap should have been part of std first...but I
presume this project's aim is to correct this omission?  :-)

Ray