Re: [boost] [gsoc] heaps

Subject: Re: [boost] [gsoc] heaps
From: David Abrahams (dave_at_[hidden])
Date: 2010-06-11 10:57:00

At Fri, 11 Jun 2010 23:07:19 +0900,
Raymond Wan wrote:
> 
> > 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?  :-)

Don't forget, the standard also has heap algorithms that use the same
default sort criterion.

-- 
Dave Abrahams
BoostPro Computing
http://www.boostpro.com