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


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk