On Fri, Jun 10, 2011 at 3:07 AM, Tim Blechmann <tim@klingt.org> wrote:
hi andrew,
1) Is it possible to iterate through the heap in order of priority with an iterator?
at the moment it is not possible to iterate the heap in order ... i have been thinking that this may be useful in some cases, however this can only be achieved by increasing the complexity of iterators (in fact every iterator will require a priority queue of possible `next' objects). however it would also simplify heap comparison ...
Also, if one wanted to go through the heap in order of priority in a convenient manner without removing elements it would be very helpful. The simplified heap comparison is definitely an added bonus. I'm also curious how that additional priority queue internal to the iterator would do in terms of memory and runtime performance.
2) What advantages to the increase() and decrease() functions provide?
efficiency: in some cases it is more efficient to call `increase' or `decrease' ...
I wouldn't expect everyone using the library to know the intimate details of each heap algorithm, so perhaps specifying what the 'best' way to perform certain common operations on each heap implementation in the documentation is a good idea. I suspect that people may try the various implementations to see what is fastest for their use case, so anything that can help making the best design and implementation choices easy could be helpful.
I also have a few suggestions for improving the documentation:
In http://tim.klingt.org/boost_heap/heap/concepts.html the note: boost.heap implements priority queues as max-heaps. While many textbooks and papers are formulated for min-heaps. Using max-heaps is consistent with the STL heap functions, though. would be better written as: boost.heap implements priority queues as max-heaps to be consistent with the STL heap functions. This is in contrast with the typical textbook design, which uses min-heaps.
:) sounds better ... i am not a native speaker, so some of my sentences may not be the best english ...
I made a mistake in this one: boost.heap implements priority queues as max-heaps to be consistent with the STL heap functions. This is in contrast [to] the typical textbook design, which uses min-heaps.
You mentioned: | please note, that you *have* to call update before modifying any | other
node. This should be made more explicit in the documentation
i will extend the documentation of `mutability' and add links from the class reference of (update/increase/decrease) to the `mutability' page. that will hopefully make things clearer ...
cheers, tim
Great, thanks! Cheers! Andrew Hundt