Subject: [boost] [heap] A few questions
From: Andrew Hundt (athundt_at_[hidden])
Date: 2011-06-10 00:17:56
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