Boost C++ Libraries Home Libraries People FAQ More

PrevUpHomeNext

Data Structures

Data Structure Configuration

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_heap

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

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

Skew 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 11.1. Comparison of amortized complexity

top()

push()

pop()

update()

increase()

decrease()

erase()

merge_and_clear()

boost::heap::priority_queue

O(1)

O(log(N))

O(log(N))

n/a

n/a

n/a

n/a

O((N+M)*log(N+M))

boost::heap::d_ary_heap

O(1)

O(log(N))

O(log(N))

O(log(N))

O(log(N))

O(log(N))

O(log(N))

O((N+M)*log(N+M))

boost::heap::binomial_heap

O(1)

O(log(N))

O(log(N))

O(log(N))

O(log(N))

O(log(N))

O(log(N))

O(log(N+M))

boost::heap::fibonacci_heap

O(1)

O(1)

O(log(N))

O(log(N)) [a]

O(1)

O(log(N))

O(log(N))

O(1)

boost::heap::pairing_heap

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

boost::heap::skew_heap

O(1)

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 update_lazy() method, which has O(log(N)) amortized complexity as well, but does not try to consolidate the internal forest


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.


PrevUpHomeNext