Subject: Re: [boost] [gsoc] heaps
From: Raymond Wan (r.wan_at_[hidden])
Date: 2010-06-11 09:42:10
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!
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk