[boost] [heap] A few questions

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