Boost
C++ Libraries
...one of the most highly
regarded and expertly designed C++ library projects in the
world.
— Herb Sutter and Andrei
Alexandrescu, C++
Coding Standards
Boost
C++ Libraries
...one of the most highly
regarded and expertly designed C++ library projects in the
world.
— Herb Sutter and Andrei
Alexandrescu, C++
Coding Standards
boost.heap provides the following data structures:
boost::heap::priority_queue
The priority_queue
class is a wrapper to the stl heap functions. It implements a heap as
container adaptor ontop of a std::vector and is immutable.
boost::heap::d_ary_heap
D-ary heaps
are a generalization of binary heap with each non-leaf node having N
children. For a low arity, the height of the heap is larger, but the
number of comparisons to find the largest child node is bigger. D-ary
heaps are implemented as container adaptors based on a std::vector.
The data structure can be configured as mutable. This is achieved by storing the values inside a std::list.
boost::heap::binomial_heapBinomial heaps are node-base heaps, that are implemented as a set of binomial trees of piecewise different order. The most important heap operations have a worst-case complexity of O(log n). In contrast to d-ary heaps, binomial heaps can also be merged in O(log n).
boost::heap::fibonacci_heap
Fibonacci heaps
are node-base heaps, that are implemented as a forest of heap-ordered
trees. They provide better amortized performance than binomial heaps.
Except pop() and erase(), the most
important heap operations have constant amortized complexity.
boost::heap::pairing_heapPairing heaps are self-adjusting node-based heaps. Although design and implementation are rather simple, the complexity analysis is yet unsolved. For details, consult:
Pettie, Seth (2005), "Towards a final analysis of pairing heaps", Proc. 46th Annual IEEE Symposium on Foundations of Computer Science, pp. 174–183
boost::heap::skew_heapSkew heaps are self-adjusting node-based heaps. Although there are no constraints for the tree structure, all heap operations can be performed in O(log n).
Table 15.1. Comparison of amortized complexity
|
|
|
|
|
|
|
|
|
|
|---|---|---|---|---|---|---|---|---|
|
|
O(log(N)) |
O(log(N)) |
n/a |
n/a |
n/a |
n/a |
O((N+M)*log(N+M)) |
|
|
|
O(log(N)) |
O(log(N)) |
O(log(N)) |
O(log(N)) |
O(log(N)) |
O(log(N)) |
O((N+M)*log(N+M)) |
|
|
|
O(log(N)) |
O(log(N)) |
O(log(N)) |
O(log(N)) |
O(log(N)) |
O(log(N)) |
O(log(N+M)) |
|
|
|
O(1) |
O(log(N)) |
O(log(N)) [a] |
O(1) |
O(log(N)) |
O(log(N)) |
O(1) |
|
|
|
O(2**2*log(log(N))) |
O(log(N)) |
O(2**2*log(log(N))) |
O(2**2*log(log(N))) |
O(2**2*log(log(N))) |
O(2**2*log(log(N))) |
O(2**2*log(log(N))) |
|
|
|
O(log(N)) |
O(log(N)) |
O(log(N)) |
O(log(N)) |
O(log(N)) |
O(log(N)) |
O(log(N+M)) |
|
[a]
The fibonacci a | ||||||||
The data structures can be configured with Boost.Parameter-style templates.
boost::heap::compare
Predicate for defining the heap order, optional (defaults to boost::heap::compare<std::less<T>
>)
boost::heap::allocator
Allocator for internal memory management, optional (defaults to boost::heap::allocator<std::allocator<T>
>)
boost::heap::stable
Configures the heap to use a stable
heap order, optional (defaults to boost::heap::stable<false>).
boost::heap::mutable_
Configures the heap to be mutable. boost::heap::d_ary_heap
and boost::heap::skew_heap
have to be configured with this policy to enable the mutability
interface.
boost::heap::stability_counter_type
Configures the integer type used for the stability counter, optional
(defaults to boost::heap::stability_counter_type<boost::uintmax_t>).
For more details, consult the Stability
section.
boost::heap::constant_time_size
Specifies, whether size() should have linear or
constant complexity. This argument is only available for node-based
heap data structures and if available, it is optional (defaults to
boost::heap::constant_time_size<true>)
boost::heap::arity
Specifies the arity of a d-ary heap. For details, please consult the
class reference of boost::heap::d_ary_heap
boost::heap::store_parent_pointer
Store the parent pointer in the heap nodes. This policy is only available
in the boost::heap::skew_heap.