data-structures - 二元堆与 D 元堆

Question

我已经读过二元堆在删除最小操作时更快，而 d-ary 堆在降低优先级操作时更快(虽然我不明白为什么)，但是我还读到了 4 堆在它们都与二进制堆相比。

那么什么时候使用二元堆，什么时候使用 d-ary 堆呢？我如何决定 d 堆的 d 应该是什么？

Answer 1

我相信，这里有几个不同的因素在起作用，使您所做的所有陈述成为真实。

要了解为什么会这样，让我们​​首先考虑 d-ary 堆中的减键是如何工作的(我们不需要单独讨论二元堆，因为二元堆只是一个 2 元堆)。在执行减少键时，我们更改树中节点的优先级，然后反复将其与其父节点交换，直到它到达树的根或它的优先级最终变得小于其父节点的优先级。在最坏的情况下，我们必须进行交换的次数由 d-ary 堆的高度给出。由于 d-ary 堆的每一层中的节点数在每一步都以 d 的因子呈指数增长，因此 d-ary 堆的高度为 O(logd n) = O(log n/log d)。这意味着如果增加 d 的值，d-ary 堆的高度会降低，因此减少键和插入将花费更少的时间。如果你考虑一个极端情况，如果你有一个 10100 进制的堆，树中的层数将比二进制堆中的层数少大约 100 倍，因此减少键或插入将快大约 100 倍。

另一方面，考虑出列操作将如何工作。为了执行出队，我们交换根的最后一个叶子，然后重复执行以下操作:我们扫描当前节点的所有子节点，如果其中任何一个小于当前节点，我们将当前节点与最小的 child 。这些迭代中的每一次都需要进行 O(d) 次总比较才能找到最小的 child ，迭代次数由树中的层数给出，我们之前看到的是 O(log n/log d)。这意味着在 d-ary 堆中出队的成本是 O(d log n/log d)。由于 d 的增长速度比 log d 快得多(实际上是指数级更快)，随着我们增加 d，出队的渐进成本和实际成本开始上升。例如，在一个 10100 元的堆中，您可能必须在每一步将每个节点与 10100 个子节点进行比较，这将花费很长时间!因此，随着 d 越来越大，d-ary 堆的出队速度往往比二进制堆慢得多。

现在回到你的最后一个问题:鉴于这里的信息，四元堆怎么可能会胜过二元堆？我将完全诚实地说，我不知道这是否属实，但它 (a) 可能取决于硬件，并且 (b) 不会让我感到惊讶。请记住，前面的所有分析都试图通过查看堆中的层数和交换次数等数量来限制 d-ary 堆操作的成本。但是，这遗漏了许多其他因素，例如寻找 parent 和子女的成本以及引用地点。对于第一个，请注意，在 d-ary 堆中，您可以通过将索引除以 d 来找到您的父节点。对于 d 是 2 的完美幂，这可以通过简单、廉价的位移来实现(因为 n/2k = n >> k)。对于奇数或不是 2 的幂的数字，这需要除法，这(在某些体系结构中)比位移更昂贵。此外，还有引用地点的影响。现在的计算机在内存中有大量的缓存层，访问缓存中的内存的成本可能比访问不在缓存中的内存的成本快数百或数千倍。当您增加 d 元堆中 d 的值时，树中的层数会减少，并且访问的元素会更靠近，从而提供更好的局部性。找到最佳点可能需要一些实验，如果碰巧 d = 4 在您的机器上是最好的，那么就去做吧!

编辑 :正如@moreON 指出的那样，对于 d = 4，堆中的层数减少了两倍，之后的比较次数增加了两倍，这实际上可能会提供更好的整体性能，因为缓存效果和较低的整体树高度。因此，它可能是优于二元堆的一个很好的候选者。

希望这可以帮助!