二叉堆与 d 叉堆
Binary heaps vs d-ary heaps
我读到二进制堆在删除最小操作时速度更快，而 d 元堆在降低优先级操作时速度更快（虽然我不明白为什么），但后来我也读到 4 -与二进制堆相比，堆在这两个方面都更快。
那么什么时候用二叉堆，什么时候用d叉堆呢？我如何决定 d 元堆的 d 应该是多少？
这里有几个不同的因素在起作用，我相信，可以使您所做的所有陈述都是真实的。
要了解这是为什么，让我们首先考虑 decrease-key 在 d-ary 堆中的工作原理（我们不需要单独讨论二叉堆，因为二叉堆是只是一个 2 元堆）。当执行 decrease-key 时，我们改变树中节点的优先级，然后重复将它与它的 parent 交换，直到它到达树的根或者它的优先级最终变得小于它的优先级 parent。在最坏的情况下，我们必须进行交换的次数由 d-ary 堆的高度决定。由于 d-ary 堆的每一层中的节点数在每一步都以因子 d 呈指数增长，因此 d-ary 堆的高度为 O(logd n) = O(log n / log d)。这意味着如果增加 d 的值，d-ary 堆的高度将减少，因此 decrease-keys 和插入将花费更少的时间。如果你考虑一个极端的情况，如果你有一个 10100-ary 堆，树中的层数将比二叉堆中的层数少大约 100 倍，所以 decrease-key 或 insert 将快约 100 倍。
另一方面，想想出列操作是如何工作的。为了执行出列，我们将最后一个叶子交换为根，然后重复执行以下操作：我们扫描当前节点的所有 children，如果其中任何一个小于当前节点，我们交换children 中最小的当前节点。这些迭代中的每一个都需要 O(d) 总比较才能找到最小的child，迭代次数由树中的层数给出，我们之前看到的是 O(log n /记录 d)。这意味着 d-ary 堆中出列的成本是 O(d log n / log d)。由于 d 的增长速度比 log d 快得多（实际上呈指数级增长），随着 d 的增加，出列的渐近成本和实际成本开始上升。例如，在 10100 元堆中，您可能必须在每一步将每个节点与 10100 children 进行比较，这将需要很长时间！因此，随着 d 越来越大，d-ary 堆的出队速度往往比二叉堆慢得多。
现在回答您的最后一个问题：根据此处的信息，四元堆怎么可能仍然优于二元堆？我将非常诚实地说，我不知道这是否属实，但它 (a) 可能取决于硬件，并且 (b) 不会让我感到惊讶。请记住，所有前面的分析都试图通过查看堆中的层数和交换次数等数量来限制 d-ary 堆操作的成本。然而，这遗漏了许多其他因素，例如寻找 parents 和 children 的成本以及参考地点。对于其中的第一个，请注意在 d-ary 堆中，您可以通过将索引除以 d 来找到 parent 节点。对于 2 的完美幂的 d，这可以通过简单、廉价的位移来实现（因为 n / 2k = n >> k）。对于奇数或不是 2 的幂的数字，这需要除法，这（在某些体系结构中）比位移更昂贵。此外，还有参考地点的影响。如今的计算机在内存中有大量的缓存层，访问缓存中的内存的成本可能比访问不在缓存中的内存的成本快数百或数千倍。当您增加 d-ary 堆中 d 的值时，树中的层数会减少，并且访问的元素会更靠近，从而提供更好的局部性。找到最佳位置可能需要进行一些实验，如果碰巧 d = 4 是您机器上最好的，那就去做吧！
EDIT：正如@moreON 指出的那样，对于 d = 4，堆中的层数减少了两倍，以后的比较次数也减少了增加两倍，这实际上可能会由于缓存效应和较低的整体树高度而提供更好的整体性能。因此，它可能是胜过二进制堆的一个很好的候选者。
希望对您有所帮助！
理论上四元堆比二元堆快
inference
function graph
由于3元堆在a中成本较大，且f(k=4) < f(k=2)，所以理论上4元堆最快。 (f(k=2) 近似于 f(k=4))
我读到二进制堆在删除最小操作时速度更快，而 d 元堆在降低优先级操作时速度更快（虽然我不明白为什么），但后来我也读到 4 -与二进制堆相比，堆在这两个方面都更快。
那么什么时候用二叉堆，什么时候用d叉堆呢？我如何决定 d 元堆的 d 应该是多少？
这里有几个不同的因素在起作用，我相信，可以使您所做的所有陈述都是真实的。
要了解这是为什么，让我们首先考虑 decrease-key 在 d-ary 堆中的工作原理（我们不需要单独讨论二叉堆，因为二叉堆是只是一个 2 元堆）。当执行 decrease-key 时，我们改变树中节点的优先级，然后重复将它与它的 parent 交换，直到它到达树的根或者它的优先级最终变得小于它的优先级 parent。在最坏的情况下，我们必须进行交换的次数由 d-ary 堆的高度决定。由于 d-ary 堆的每一层中的节点数在每一步都以因子 d 呈指数增长，因此 d-ary 堆的高度为 O(logd n) = O(log n / log d)。这意味着如果增加 d 的值，d-ary 堆的高度将减少，因此 decrease-keys 和插入将花费更少的时间。如果你考虑一个极端的情况，如果你有一个 10100-ary 堆，树中的层数将比二叉堆中的层数少大约 100 倍，所以 decrease-key 或 insert 将快约 100 倍。
另一方面，想想出列操作是如何工作的。为了执行出列，我们将最后一个叶子交换为根，然后重复执行以下操作：我们扫描当前节点的所有 children，如果其中任何一个小于当前节点，我们交换children 中最小的当前节点。这些迭代中的每一个都需要 O(d) 总比较才能找到最小的child，迭代次数由树中的层数给出，我们之前看到的是 O(log n /记录 d)。这意味着 d-ary 堆中出列的成本是 O(d log n / log d)。由于 d 的增长速度比 log d 快得多（实际上呈指数级增长），随着 d 的增加，出列的渐近成本和实际成本开始上升。例如，在 10100 元堆中，您可能必须在每一步将每个节点与 10100 children 进行比较，这将需要很长时间！因此，随着 d 越来越大，d-ary 堆的出队速度往往比二叉堆慢得多。
现在回答您的最后一个问题：根据此处的信息，四元堆怎么可能仍然优于二元堆？我将非常诚实地说，我不知道这是否属实，但它 (a) 可能取决于硬件，并且 (b) 不会让我感到惊讶。请记住，所有前面的分析都试图通过查看堆中的层数和交换次数等数量来限制 d-ary 堆操作的成本。然而，这遗漏了许多其他因素，例如寻找 parents 和 children 的成本以及参考地点。对于其中的第一个，请注意在 d-ary 堆中，您可以通过将索引除以 d 来找到 parent 节点。对于 2 的完美幂的 d，这可以通过简单、廉价的位移来实现（因为 n / 2k = n >> k）。对于奇数或不是 2 的幂的数字，这需要除法，这（在某些体系结构中）比位移更昂贵。此外，还有参考地点的影响。如今的计算机在内存中有大量的缓存层，访问缓存中的内存的成本可能比访问不在缓存中的内存的成本快数百或数千倍。当您增加 d-ary 堆中 d 的值时，树中的层数会减少，并且访问的元素会更靠近，从而提供更好的局部性。找到最佳位置可能需要进行一些实验，如果碰巧 d = 4 是您机器上最好的，那就去做吧！
EDIT：正如@moreON 指出的那样，对于 d = 4，堆中的层数减少了两倍，以后的比较次数也减少了增加两倍，这实际上可能会由于缓存效应和较低的整体树高度而提供更好的整体性能。因此，它可能是胜过二进制堆的一个很好的候选者。
希望对您有所帮助！
理论上四元堆比二元堆快
inference
function graph
由于3元堆在a中成本较大，且f(k=4) < f(k=2)，所以理论上4元堆最快。 (f(k=2) 近似于 f(k=4))