hi all, since the heaps/queues project is likely to be used by multiple people, i think it may be a good idea to share some ideas on the list ... for now, i have been implementing a (non-intrusive) d-ary heap, which was very useful to do some prototyping of the actual interface. all data structures support the following template arguments: typename T // value type bool stable // stability class Cmp // compare object class Alloc // allocator for internal data structures the interface matches the forward container requirement, except that it does not support iterators (only const_iterators) and container comparison. at the moment, i distinguish between immutable and mutable heaps. the interface for immutable heaps would look like this: class immutable_heap { public: // priority queue support value_type const & top(void) const; void push(value_type const & v); void pop(void); // merge support void merge (immutable_heap const & rhs); void merge_and_clear (immutable_heap & rhs); // moves all elements from rhs to *this }; for mutable heaps, i have been using a `handle' to refer to specific elements: class mutable_heap { public: typedef handle_type; // priority queue support value_type const & top(void) const; handle_type push(value_type const & v); void pop(void); // update via function void update(handle_type const & node, value_type const & v); void increase(handle_type const & node, value_type const & v); void decrease(handle_type const & node, value_type const & v); // force update after element has been changed via the handle void update(handle_type const & node); void increase(handle_type const & node); void decrease(handle_type const & node); // merge support void merge (mutable_heap const & rhs); void merge_and_clear (mutable_heap & rhs); }; the forced update api is rather dangerous, since the heap would enter an undefined state, of the node is changed, but the heap is not updated. otoh, it would help to update values using a different api than the assignment operator. 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 ... the code is available from my public git repository. i would be curious to hear some thoughts! http://tim.klingt.org/git?p=boost_heap.git cheers, tim -- tim@klingt.org http://tim.klingt.org A year ago, six months ago, I thought that I was an artist. I no longer think about it, I am. Henry Miller
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
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. -- Dave Abrahams BoostPro Computing http://www.boostpro.com
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
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
Hi Dave, On Fri, Jun 11, 2010 at 23:57, David Abrahams <dave@boostpro.com> wrote:
At Fri, 11 Jun 2010 23:07:19 +0900, Raymond Wan wrote:
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.
Oh! Opps...yes, sorry, I did forget about that! Thanks! Of course, I don't know the reasons why the standard uses the > operator. Personally, I think we're just talking about things from two different ends. I'm just saying that the term "heap" doesn't imply either operator. Out of convenience, books and the C++ standard made a choice and they happened to have made different choices...but neither is more correct than the other. Likewise, if a max-heap was used to follow what std already does, then there is nothing wrong to explicitly say in the documentation that "by default" a "max-heap is built". I was just looking at some std heap documentation (to refresh my memory :-) ) and it says, "Internally, a heap is a tree where each node links to values not greater than its own value." [1] I would say that this statement is incorrect...but that's just me being picky. :-) Thank you for correcting me! Ray [1] http://www.cplusplus.com/reference/algorithm/make_heap/
participants (3)
-
David Abrahams -
Raymond Wan -
Tim Blechmann