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

来自维基

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

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

标签： data-structuresheap

大多数类型的堆每个节点最多有两个孩子并不是真的，但确实二进制堆——每个节点最多有两个孩子——是最常用的实现类型。它是最常实现的类型，因为它简单、缓存友好且内存高效。

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

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

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

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