Subject: Re: [boost] [heap] A few questions
From: Tim Blechmann (tim_at_[hidden])
Date: 2011-06-10 03:07:54
> 1) Is it possible to iterate through the heap in order of priority with
> an iterator?
at the moment it is not possible to iterate the heap in order ... i have been
thinking that this may be useful in some cases, however this can only be
achieved by increasing the complexity of iterators (in fact every iterator will
require a priority queue of possible `next' objects).
however it would also simplify heap comparison ...
> 2) What advantages to the increase() and decrease() functions provide?
efficiency: in some cases it is more efficient to call `increase' or `decrease'
> 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.
:) sounds better ... i am not a native speaker, so some of my sentences may not
be the best english ...
> 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.
some people asked for a better comparison or a table of operations and
complexity ... mutable versions of container adaptors have the same algorithmic
complexity as non-mutable, but introduce an indirection ...
> 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:
> ble.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
> This should be made more explicit in the documentation
i will extend the documentation of `mutability' and add links from the class
reference of (update/increase/decrease) to the `mutability' page. that will
hopefully make things clearer ...
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk