为什么许多类型的堆数据结构中的节点只有两个子节点？

Question

来自维基百科

每个节点可以拥有的最大子节点数取决于堆的类型，但在许多类型中最多为两个，这称为二叉堆。

我不明白为什么在许多类型中堆中的节点最多只有两个子节点？为什么三个孩子、四个孩子等等并不常见？谢谢~

Answer 1

虽然大多数类型的堆每个节点最多有两个子级，但这确实是二叉堆（每个节点最多有两个子级）是最常实现的类型。它是最常用的实现类型，因为它简单、缓存友好且内存效率高。

用于二进制堆的数据结构可以与每个节点不同数量的子节点一起使用。如果我们认为x是常数，则x元堆中的常见操作仍将花费O(log N)时间。然而，为了决定最好的x，我们必须让它变化，在这种情况下，常见操作需要O(x * log N / log x)时间。

为了确定每个节点最有效的子节点数量，我们可以选择x来最小化因子x/log x。

如果绘制该图，您可以看到每个节点的最佳子节点数实际上是 3（最小值为 x=e，但我们需要一个整数）：

...但是 2 和 3 之间的差异并不显着，并且每个节点使用 2 个子节点的代码更简单，因此这是常见的做法。