0
  1. 与使用 k-ary heap 实现的 (Max-heapify) 相关的运行时是多少。
  2. 渐近地说，k-ary heap 比二叉堆更有效吗？
  3. 在实践中，k-ary heap 是否比二叉堆更有效？
  4. 可以将搜索树实现为 k 数组吗？
4

1 回答 1

0

你问了很多问题，所以我会尝试依次回答所有问题。

  1. k-ary heap 上的 heapify 操作的运行时间是 O(n)，它与 ​​k 无关。这不是很明显，但大多数介绍性算法教科书都证明了 k = 2 的情况。

  2. 让我们对一般的 k 元堆进行分析，然后我们可以通过设置 k = 2 将其与二进制堆进行比较。在 k 元堆中，find-min 操作的成本为 O(1) (只需查看堆的顶部），heapify 操作的成本为 O(n)，如上所述。当向 k-ary 堆添加新元素时，运行时间与堆的高度成正比，即 O(log kn) = O(log n / log k)（使用对数的基数变化公式得出）。在 big-O 表示法中包含对数的底并不常见，但在这种情况下，因为 k 是一个参数，我们不能忽略它的贡献。在 extract-min 操作中，我们需要从树的顶部向下工作。在每个级别，我们最多查看当前节点的 k 个子节点以找到最大的子节点，然后可能进行向下交换。这意味着每层有 O(k) 个工作，并且有 O(log n / log k) 个层，所以完成的工作是 O(k log n / log k)。渐近地，对于任何固定的 k，这些操作的运行时间分别为 O(1)、O(n)、O(log n) 和 O(log n)，因此 k-ary heap 和二叉堆。

  3. 但在实践中，还是有区别的。看到这一点的一种好方法是使 k 非常非常大（例如 10 100）。在这种情况下，删除的成本会非常大，因为每个节点最多有10100个子节点，这将使相应二叉树的高度相形见绌。对于 k 的中间值（k = 3 或 4），实际上使用 3 元或 4 元树可能比二叉树更快，但实际上最好的找出方法是剖析看看会发生什么。引用位置、缓存和划分速度等因素的相互作用都将相互竞争以影响运行时间。

  4. 是的！有诸如多路搜索树之类的东西。其中最著名的之一是B-tree，它实际上是一个非常有趣的数据结构。

希望这可以帮助！

于 2015-06-23T22:03:23.013 回答