...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
Dary heaps
are a generalization of binary heap with each nonleaf 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. Dary
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_heap
Binomial heaps are nodebase heaps, that are implemented as a set of binomial trees of piecewise different order. The most important heap operations have a worstcase complexity of O(log n). In contrast to dary heaps, binomial heaps can also be merged in O(log n).
boost::heap::fibonacci_heap
Fibonacci heaps
are nodebase heaps, that are implemented as a forest of heapordered
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_heap
Pairing heaps are selfadjusting nodebased 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_heap
Skew heaps are selfadjusting nodebased heaps. Although there are no constraints for the tree structure, all heap operations can be performed in O(log n).
Table 13.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.Parameterstyle 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 nodebased
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 dary 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
.