boost :: heap :: arity，它是什么？

Question

我在清理遗留代码。里面我有一个优先级队列，从1986年^ _ ^。 将它与C++接口进行接口后，与标准符合得越来越差。我在“市场”（std + boost）的所有priority_queues之间做了一些基准。

Boost提供了一个priority_queue名称boost::d_ary::heap。这个队列需要一个名为boost::heap::arity<int>的参数，Boost的文档没有提供明确的解释，只是一个链接到堆的实现。

目前我把boost::heap::arity<128>我真的很满意，但我不知道这是什么意思。你们其中一位有点解释吗？

Answer 1

通常优先级队列实现为heaps。堆满了部分顶部的树。这种完整的树通常存储在一个数组中。 arity描述了树中每个节点至多有多少个孩子。对于二元树来说，树是一棵二叉树，等等。从抽象的角度来看，对应于堆的树的深度大约为log(n)/log(d)（其中d是堆的阵营）。

堆的性能（理论上）取决于arity，实际上最重要的是缓存效率。你应该运行一些基准来测试性能。我认为128的值是相当高的，我个人使用范围从2到16.