为什么我们不使用三元堆或四元堆？

Question

我做了一些计算，似乎三元堆总是优于二元堆，而四元堆有时会优于三元堆。

令c、s分别表示比较和交换所需的时间。假设我们有一个长度为 n 的 k 元堆。堆支持两种基本操作：

1. 插入。假设您要向上传播，这需要 log_k(n)*(c + s) 时间，这对于较大的 k 来说总是更好（这是有道理的，因为对于较大的 k，堆的结构较差。）
2. 最大提取量 这需要 log_k(n) * (kc + s) 时间。我不知道如何在这里做 LaTeX，所以我不会写出方程，但请相信我说，对于 c = s，最小值出现在 k = 3.59 处，最小值仅取决于 c / s 的比率。对于较大的 c，最小值出现在较小的 k 处。

然而，这就是我真正困惑的地方：比较 k = 2 和 3，您实际上会发现对于提取最大值和插入， 3总是比 2 更好。（我也不会写出方程，但这部分是因为 3^2 > 2^3）。

那么我们为什么不使用三元堆呢？为什么我们总是使用二叉堆？

Answer 1

事实上，我们确实使用三元或四元堆。一般来说，它被称为d 进制堆。你是对的：理论上，3 堆应该比 2 堆更快，4 堆应该和 2 堆一样快。我在博客http://blog.mischel.com/2013/10/05/the-d-ary-heap/中写了一些相关内容。

\n\n

\n

应该清楚的是，将项目添加到 4 堆会比将项目添加到相同大小的 2 堆更快。例如，如果您想要向上面所示的 4 堆添加一个项目，BubbleUp 最多会执行 3 次迭代。具有 20 个节点的二叉堆需要 5 个级别，这意味着您可能需要进行最多 5 次迭代。

\n\n

不过，没有什么\xe2\x80\x99s是免费的。移除变得更加昂贵。尽管级别较少，但随着 d 的增加，SiftDown 方法中循环的每次迭代都会花费更长的时间。对于二叉堆，您只需在每次迭代时进行两个节点比较（查找最小子节点需要进行一次比较，而将您插入的节点与最小子节点进行比较则需要进行另一个比较） ）。4 堆需要筛选的级别较少，但每个级别都需要更多处理，因为它必须进行四次比较才能找到最小的子级。

\n

\n\n

不幸的是，渐近分析并不是故事的全部。二进制堆允许您实现一些在 3 堆及更高堆中不可能实现的快捷方式。随着堆的顺序增加，当你筛选堆时找到最小的孩子会变得越来越昂贵，并且这会抵消大部分理论上的性能增益。

\n\n

在我的实验中，我发现 3 堆几乎总是比二进制堆更快，尤其是当比较非常昂贵时。在某些情况下，4 堆和 5 堆的性能优于 3 堆，但还不足以值得使用它们。

\n\n

对于我自己的工作，我几乎总是使用优化的三元堆，因为它通常比我的优化的二进制堆更快。但我已经设置了代码，因此我所要做的就是更改一行以从三元堆转换为二进制堆。

\n

Answer 2

“我们”确实使用四元堆： https://learn.microsoft.com/en-us/dotnet/api/system.collections.generic.priorityqueue-2 ?view=net-6.0