algorithm - 对 removeMin() 的调用将在 7 叉树的最大堆中进行多少次比较？

Question

假设具有 10^6 个元素的最大堆存储在完整的 7 叉树中。调用removeMin() 大约会进行多少次比较？

• 5000
• 50
• 10^6
• 500
• 5

我的解决方案：比较的数量最多应该等于叶节点的数量，因为在最大堆中，最小。可以在任何不在上述选项中的叶节点上找到。更好的方法是取 (log of 10^6 to base 7) 的平方，得到 50，但这仅在我们确定最小元素将跟随树上的单个分支时，在最大堆的情况下不是正确的。我希望你能提供帮助。

标签： algorithmdata-structurestreelanguage-agnosticmax-heap

Answer 1

没有“自然”的方法可以从最大堆中删除最小值。您只需查看所有叶节点即可确定哪一个恰好是最小值。

那么问题是有多少叶节点。直观地说，我们预计堆中叶子节点的比例非常接近节点总数。将其发挥到极致 - 如果您有一个 1,000,000 元堆，那么您将在顶层拥有一个节点，而在下一层拥有所有剩余的 999,999 个元素。即使在堆是二进制堆的最小情况下，您也会期望大约一半的元素位于底层。

更具体地说，让我们做一些数学运算！一个有 n 个节点的 7 元堆有多少叶子？那么，树中的每个节点要么

• 成为一片叶子，或
• 有七个孩子，

一个可能的例外是，由于最底部的行可能未满，因此可能有一个节点的子节点少于七个。由于这只是一次性的，当我们处理数百万个元素时，我们可以忽略最后一个节点。一个快速的归纳证明可以用来证明每个节点没有子节点或七个子节点的任何树的叶节点数量是内部节点的七倍（证明这一点！），所以我们期望比（7/8 )ths 节点将是叶子，总共有 875,000 个叶子要检查。

因此，这里的最佳答案将是大约 10 ⁶次比较。