I was looking through the Boost.Heap documentation, and I came up with a couple questions: 1) Is it possible to iterate through the heap in order of priority with an iterator? 2) What advantages to the increase() and decrease() functions provide? 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. http://tim.klingt.org/boost_heap/heap/data_structures.html Can you provide runtime complexity constraints for each of these data structures? Particularly if the mutable version has different performance from the standard version of each. spelling: For a low arity, the h[e]ight of the heap is larger improved wording: In analogy to d-ary heaps, boost-heaps also provides an mutable version at the cost of an indirection. would be better as: The b_heap_mutable<http://tim.klingt.org/boost_heap/boost/heap/d_ary_heap_mutable.html> class stores the values inside a std::list in order to achieve mutability. You mentioned: | please note, that you *have* to call update before modifying any other node. This should be made more explicit in the documentation Overall this library looks extremely useful. Good work! Cheers! Andrew Hundt
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 ...
2) What advantages to the increase() and decrease() functions provide?
efficiency: in some cases it is more efficient to call `increase' or `decrease' ...
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 ...
http://tim.klingt.org/boost_heap/heap/data_structures.html Can you provide runtime complexity constraints for each of these data structures? Particularly if the mutable version has different performance from the standard version of each.
some people asked for a better comparison or a table of operations and complexity ... mutable versions of container adaptors have the same algorithmic complexity as non-mutable, but introduce an indirection ...
spelling: For a low arity, the h[e]ight of the heap is larger
thnx
improved wording: In analogy to d-ary heaps, boost-heaps also provides an mutable version at the cost of an indirection. would be better as: The b_heap_mutable<http://tim.klingt.org/boost_heap/boost/heap/d_ary_heap_muta ble.html> class stores the values inside a std::list in order to achieve mutability.
thnx
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
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
Andrew Hundt wrote:
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.
Isn't iteration in order of priority completely opposite to the very idea of a heap (="unordered pile")? If you want/need that, isn't a std::map more suitable for your use case?
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.
Isn't iteration in order of priority completely opposite to the very idea of a heap (="unordered pile")? If you want/need that, isn't a std::map more suitable for your use case?
actually a treap (like boost::intrusive::treap) would be the most efficient data structure for that. otoh, one of the ideas behind boost.heap is to emulate a specific functionality if it is not supported out of the box. e.g. it supports merging of all heaps, no matter if they can be merged efficiently or not ... tim
On Fri, Jun 10, 2011 at 11:46 AM, Thomas Klimpel < Thomas.Klimpel@synopsys.com> wrote:
Andrew Hundt wrote:
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.
Isn't iteration in order of priority completely opposite to the very idea of a heap (="unordered pile")? If you want/need that, isn't a std::map more suitable for your use case? _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
I believe a heap is more like a partially ordered pile than an unordered pile. If you are attempting to perform heap sort or perform tasks in order of priority from highest to lowest wouldn't a heap be appropriate? In those cases I was thinking that iterating over the heap in order of priority would make sense as an alternative to calling pq.pop() repeatedly. Such an iterator could make something like copying the contents of the heap into another object such as a vector in sorted order as easy as a call to std::copy(pq.sorted_begin(),pq.sorted_end(),std::back_inserter(vec)). Perhaps an iterator adapter that achieves this effect would be more appropriate? I may be missing something important like a major performance disadvantage or an existing way to accomplish this that is definitively better. However, I don't think a std::map would be appropriate in all cases, since the runtime complexity of various operations of a std::map isn't always the same as the runtime complexity in each heap implementation. Cheers! Andrew Hundt
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.
it depends on the heap layout ...
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.
in general people are adviced to specify the direction of the update. if they know they will only increase or decrease the key, they should use that version. for `update(handle_type), value_type)' the effect is less crucial, since it mainly avoids one comparison inside `update'. for `update(handle_type)' there is no way to find the direction of the update, so some implementations will use a worse codepath than actually required ...
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.
that is my main idea :) cheers, tim
Andrew Hundt wrote:
1) Is it possible to iterate through the heap in order of priority with an iterator?
No - but the question raises an interesting issue. If you want to iterate in-order through an entire heap efficiently, you should sort the underlying sequence using std::sort_heap and then iterate through the result. Clearly that's incompatible with providing a simple iterator interface. You might want those iterators so that you can iterate through just a small part of the heap. For example, I have some code that uses std::partial_sort to sort just enough of a large std::vector to satisfy current requirements; this is used to display a scrollable list of search results, where the common case is that the user only looks at the first screenful (PSEUDO_CODE): template <typename T> class vector_sorted_on_demand { std::vector<T> impl; size_t n_sorted; public: void push_back(const T& val) { impl.push_back(val); n_sorted = 0; // This suits the case where everything is added before anything is read. } T operator[](size_t idx) { if (idx >= n_sorted) { size_t n_to_sort = n_sorted/2 + 10; // or whatever size_t mid = std::max( idx, std::min(n_sorted + n_to_sort, impl.size()) ); std::partial_sort(impl.begin()+n_sorted, impl.begin()+mid, impl.end()); n_sorted = mid; } return impl[idx]; } }; I could imagine instead maintaining the unsorted portion as a heap, with some complexity trade-offs. It seems to me that this sort of thing is best done using an explicit "underlying container" i.e. std::vector, with algorithms on top of it. A heap container with iterators just doesn't seem such a good fit: it maintains the heap predicate safely, but I don't always want that. This makes me wonder whether Tim's proposed alternative heap structures should perhaps be decomposed slightly, to expose algorithms in the style of std::push|pop_heap. Without that, I can't use e.g. the b_heap in this style of "part heap, part sorted" hybrid container. Is extracting algorithms practical? Regards, Phil.
participants (4)
-
Andrew Hundt -
Phil Endecott -
Thomas Klimpel -
Tim Blechmann