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

Question

我正在清理遗留代码。在里面，我有一个1986年^_^的优先级队列。在将其与C++接口对接之后，它或多或少地符合标准。我在市场上所有的priority_queues之间做了一些基准测试(std + boost)。

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

现在我放了boost::heap::arity<128>，我真的很满意，但我不知道它是什么意思。你们中的一个，有没有什么解释？

Answer 1

优先级队列通常被实现为heaps。堆是具有顶部部分顺序的完整树。这样的完整树通常存储在数组中。稀疏性描述了树的每个节点最多有多少个子节点。对于2的情况，树是二叉树，依此类推。从抽象的角度来看，对应于堆的树的深度大约是log(n)/log(d) (其中d是堆的数量)。

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