Hi David, On Fri, Jun 11, 2010 at 22:53, David Abrahams <dave@boostpro.com> wrote:
At Fri, 11 Jun 2010 22:42:10 +0900, Raymond Wan wrote:
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 ...
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