Boost logo

Boost :

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
  2) What advantages to the increase() and decrease() functions provide?

I also have a few suggestions for improving the documentation:

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.
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

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<>
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
This should be made more explicit in the documentation

Overall this library looks extremely useful. Good work!

Andrew Hundt

Boost list run by bdawes at, gregod at, cpdaniel at, john at