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

Question

来自维基

The maximum number of children each node can have depends on the type of heap, but in many types it is at most two, which is known as a binary heap.

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

Answer 1

大多数类型的堆每个节点最多有两个 child 是不正确的，但二叉堆是真实的——确实每个节点最多有两个 child ——是最多的通常实现的类型。它是最常实现的类型，因为它简单、缓存友好且内存效率高。

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

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

如果你绘制你可以看到每个节点的最佳子节点数实际上是 3(最小值是 x=e，但我们需要一个整数):

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