Data Structures

| Home | Libraries | People | FAQ | More

## Data Structures

`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 14.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

### Data Structure Configuration

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