Hi Tim, On Fri, Jun 11, 2010 at 21:48, Tim Blechmann <tim@klingt.org> 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