我读过二进制堆在删除最小操作时更快，而 d-ary 堆在降低优先级操作时更快（虽然我不明白为什么），但后来我也读到 4 堆在它们都与二进制堆相比。
那么什么时候使用二叉堆，什么时候使用二叉堆呢？我如何决定 d 应该是什么 d 堆？
问问题
3608 次
2 回答
7
这里有几个不同的因素在起作用，我相信，使你所做的所有陈述都成为真实的成为可能。
要了解这是为什么，让我们首先考虑一下 d-ary heap 中的 reduce-key 是如何工作的（我们不需要单独讨论二进制 heap，因为二进制 heap 只是一个 2-ary heap）。当执行递减键时，我们改变树中节点的优先级，然后反复将其与其父节点交换，直到它到达树的根或它的优先级最终变得小于其父节点的优先级。在最坏的情况下，我们必须进行交换的次数由 d-ary 堆的高度给出。由于 d-ary heap 的每一层中的节点数在每一步都以 d 的因子呈指数增长，因此 d-ary heap 的高度为 O(log dn) = O(log n / log d)。这意味着如果增加 d 的值，则 d-ary 堆的高度会降低，因此减少键和插入将花费更少的时间。如果你考虑一个极端的情况，如果你有一个 10 100的堆，树中的层数将比二叉堆中的层数少大约 100 倍，因此减少键或插入将快大约 100 倍.
另一方面，想想出队操作是如何工作的。为了执行出队，我们将最后一个叶子交换为根，然后重复执行以下操作：扫描当前节点的所有子节点，如果其中任何一个小于当前节点，我们将当前节点与最小的孩子。这些迭代中的每一个都需要 O(d) 总比较来找到最小的孩子，并且迭代次数由树中的层数给出，我们之前看到的是 O(log n / log d)。这意味着在 d-ary 堆中出队的成本是 O(d log n / log d)。由于 d 的增长速度比 log d 快得多（实际上是指数级地快），当我们增加 d 时，出队的渐近（和实际）成本开始上升。例如，在 10 100-ary heap，您可能必须在每一步将每个节点与 10 100个子节点进行比较，这将需要很长时间！因此，随着 d 越来越大，d-ary heap 的出队速度往往比二叉堆慢得多。
现在回答你的最后一个问题：考虑到这里的信息，4 元堆怎么可能胜过二元堆？老实说，我不知道这是否属实，但它 (a) 可能取决于硬件并且 (b) 不会让我感到惊讶。请记住，前面的所有分析都试图通过查看堆中的层数和进行的交换次数等数量来限制 d-ary 堆操作的成本。但是，这忽略了许多其他因素，例如寻找父母和孩子的成本以及参考地点。对于其中的第一个，请注意在 d-ary 堆中，您可以通过将索引除以 d 来找到父节点。对于 d 是 2 的完美幂，这可以用一个简单的方法来实现，= n >> k)。对于奇数或不是 2 的幂的数字，这需要除法，这（在某些架构中）比位移更昂贵。此外，还有参考位置的影响。如今的计算机在内存中有大量的缓存层，访问缓存中的内存的成本可能比访问不在缓存中的内存的成本快数百或数千倍。当您增加 d 堆中 d 的值时，树中的层数会减少，访问的元素会更靠近，从而提供更好的局部性。找到最佳位置可能需要一些实验，如果碰巧 d = 4 是您机器上最好的，那就去做吧！
EDIT: as @moreON pointed out, for d = 4, the number of layers in the heap goes down by a factor of two and the number of comparisons per later goes up by a factor of two, which may actually give better overall performance due to cache effects and a lower overall tree height. Therefore, it's probably a good candidate to outperform a binary heap.
Hope this helps!
于 2015-06-23T23:55:50.057 回答
0
the 4-ary heap is faster then binary heap in theory
as 3-ary heap have large cost in a, and f(k=4) < f(k=2), so 4-ary heap is fastest in theory. (f(k=2) approximate to f(k=4))
于 2018-10-17T08:35:06.147 回答