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
1) Is it possible to iterate through the heap in order of priority with an
2) What advantages to the increase() and decrease() functions provide?
I also have a few suggestions for improving the documentation:
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.
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.
For a low arity, the h[e]ight of the heap is larger
In analogy to d-ary heaps, boost-heaps also provides an mutable version at
the cost of an indirection.
would be better as:
stores the values inside a std::list in order to achieve mutability.
| please note, that you *have* to call update before modifying any other
This should be made more explicit in the documentation
Overall this library looks extremely useful. Good work!
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk