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.