boost.heap 提供以下数据结构
boost::heap::priority_queuepriority_queue 类是对 stl 堆函数的包装器。它基于 std::vector 实现堆作为容器适配器，并且是不可变的。
boost::heap::d_ary_heap
D-ary 堆 是二叉堆的推广，其中每个非叶节点都有 N 个子节点。对于低阶数，堆的高度更大，但查找最大子节点的比较次数更多。D-ary 堆作为基于 std::vector 的容器适配器实现。
数据结构可以配置为可变的。这是通过将值存储在 std::list 中实现的。
boost::heap::binomial_heap二项堆 是基于节点的堆，实现为一组不同阶的二项树。最重要的堆操作的最坏情况复杂度为 O(log n)。与 d-ary 堆相比，二项堆也可以在 O(log n) 时间内合并。
boost::heap::fibonacci_heap
斐波那契堆 是基于节点的堆，实现为堆排序树的森林。它们提供了比二项堆更好的摊销性能。除了 pop() 和 erase()，最重要的堆操作具有恒定的摊销复杂度。
boost::heap::pairing_heap配对堆 是自调整的基于节点的堆。尽管设计和实现相当简单，但复杂度分析尚未解决。详情请参考：
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斜堆 是自调整的基于节点的堆。虽然对树结构没有约束，但所有堆操作都可以在 O(log n) 时间内完成。
表 15.1. 摊销复杂度比较
|
|
|
|
|
|
|
|
|
|
|---|---|---|---|---|---|---|---|---|
|
|
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] 斐波那契堆有一个 | ||||||||
可以使用 Boost.Parameter 风格的模板配置数据结构。
boost::heap::compare定义堆顺序的谓词，可选（默认为 boost::heap::compare<std::less<T> >）
boost::heap::allocator内部内存管理的分配器，可选（默认为 boost::heap::allocator<std::allocator<T> >）
boost::heap::stable将堆配置为使用 稳定的堆顺序，可选（默认为 boost::heap::stable<false>）。
boost::heap::mutable_将堆配置为可变的。boost::heap::d_ary_heap 和 boost::heap::skew_heap 必须使用此策略配置才能启用 可变性接口。
boost::heap::stability_counter_type配置用于稳定性计数器的整数类型，可选（默认为 boost::heap::stability_counter_type<boost::uintmax_t>）。详情请参考 稳定性 部分。
boost::heap::constant_time_size指定 size() 应该具有线性复杂度还是常数复杂度。此参数仅适用于基于节点的堆数据结构，如果可用，则为可选（默认为 boost::heap::constant_time_size<true>）
boost::heap::arity指定 d-ary 堆的阶数。详情请参考 boost::heap::d_ary_heap 的类参考。
boost::heap::store_parent_pointer在堆节点中存储父指针。此策略仅在 boost::heap::skew_heap 中可用。