Re: [boost] [gsoc] heaps

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

Hi Tim,

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

I can't help you much about most of your e-mail (sorry!), but
regarding this point, I don't think one is more of a default than the
other.  Heaps can be min-heaps or max-heaps and maybe books start with
min-heaps because they have to "start somewhere".  A priority queue
should use a max-heap because one usually associates a higher number
with a higher priority.  I think if possible, both should be supported
for it to be called a heap.  If you only implement one, then rather
than calling it a heap, you should probably call it a min-heap (for
example) so that someone who uses it knows exactly what it is.  Also,
if they need a max-heap, they can adapt (i.e., by subtracting from the
maximum possible value...which is of course not always possible).

Hope this helps!

Ray