对 removeMin() 的调用将在 7 叉树的最大堆中进行多少次比较？
How many comparisons a call to removeMin() will make in max heap of 7-ary tree?
假设一个有 10^6 个元素的 max heap 存储在一个 complete 7-ary tree 中。调用 removeMin() 大约会进行多少次 比较？
- 5000
- 50
- 10^6
- 500
- 5
我的解决方法：比较的次数最多应该等于叶节点的个数，因为在max heap中，min.可以在不在上述选项中的任何叶节点处找到。更好的方法是取（以 7 为底的 10^6 的对数）的平方，它给出 50 但这只是当我们确定最小元素将遵循树的单个分支时，在最大堆的情况下不是正确的。
希望对你有所帮助。
没有 "natural" 方法可以从最大堆中删除最小值。您只需查看所有叶节点，找出哪个恰好是最小的。
接下来的问题是叶节点有多少个。直觉上，我们期望堆中叶子节点的比例非常接近节点总数。把它发挥到极限——如果你有一个 1,000,000 元的堆，你会在顶层有一个节点，而所有剩余的 999,999 个元素在下一层。即使在堆是二进制堆的最小情况下，您也会期望大约一半的元素位于底层。
更具体地说，让我们做一些数学运算！一个有 n 个节点的 7 叉堆有多少叶子？那么，树中的每个节点都会
- 是一片叶子，或者
- 有七个 children,
除了一个可能的例外，因为最底部的一行可能未满，所以可能有一个节点少于七个 children。因为那只是一个 one-off，所以当我们处理数百万个元素时，我们可以忽略最后一个节点。归纳法的快速证明可用于显示每个节点没有 children 或七个 children 的任何树的叶节点数将是内部节点数的七倍（证明这一点！），所以我们预计有 (7/8) 个节点是叶子，总共有 875,000 个叶子需要检查。
因此，这里的最佳答案大约是 106 次比较。
最小元素可以是最大堆的任何叶子或任何类型，那里没有顺序。从 A[10^6/7 + 1] 开始的所有元素（其中 A 是存储叶子的数组）都是叶子节点，需要检查。这意味着 8571412 次比较只是为了找到最小值。在那之后，没有简单的方法可以 'remove' 最小值而不引入不能通过简单地移动叶子来填充的间隙。
这是一个印刷错误。也许老师想问 removeMax，答案接近 50 -- 见下文：
由于每个节点有 7 个子节点，heapify 对每个级别进行了 7 次比较。如果 h 是堆的高度，那么就是 7*h 比较。
粗略分析：（这里~的意思是大概）
h ~ log_7(10^6) = 7.1，因此总比较 7*7.1 ~ 50
更准确的分析：
一个 7 元堆将包含以下元素：1 + 7 + 7^2 + ... + 7^h = 10^6
左边是一个几何级数，总和为：(7^h -1)/6 = 10^6
=> 7^h = 6*10^6 + 1
=> h = lg_7(6*10^6 + 1) = 8 (approximately) ，因此 7*8 = 56，仍然来自选项 50 是最接近的。
*A 是排序堆的数组。
假设一个有 10^6 个元素的 max heap 存储在一个 complete 7-ary tree 中。调用 removeMin() 大约会进行多少次 比较？
- 5000
- 50
- 10^6
- 500
- 5
我的解决方法：比较的次数最多应该等于叶节点的个数，因为在max heap中，min.可以在不在上述选项中的任何叶节点处找到。更好的方法是取（以 7 为底的 10^6 的对数）的平方，它给出 50 但这只是当我们确定最小元素将遵循树的单个分支时，在最大堆的情况下不是正确的。 希望对你有所帮助。
没有 "natural" 方法可以从最大堆中删除最小值。您只需查看所有叶节点，找出哪个恰好是最小的。
接下来的问题是叶节点有多少个。直觉上，我们期望堆中叶子节点的比例非常接近节点总数。把它发挥到极限——如果你有一个 1,000,000 元的堆，你会在顶层有一个节点，而所有剩余的 999,999 个元素在下一层。即使在堆是二进制堆的最小情况下，您也会期望大约一半的元素位于底层。
更具体地说，让我们做一些数学运算！一个有 n 个节点的 7 叉堆有多少叶子？那么，树中的每个节点都会
- 是一片叶子，或者
- 有七个 children,
除了一个可能的例外，因为最底部的一行可能未满，所以可能有一个节点少于七个 children。因为那只是一个 one-off，所以当我们处理数百万个元素时，我们可以忽略最后一个节点。归纳法的快速证明可用于显示每个节点没有 children 或七个 children 的任何树的叶节点数将是内部节点数的七倍（证明这一点！），所以我们预计有 (7/8) 个节点是叶子，总共有 875,000 个叶子需要检查。
因此，这里的最佳答案大约是 106 次比较。
最小元素可以是最大堆的任何叶子或任何类型，那里没有顺序。从 A[10^6/7 + 1] 开始的所有元素（其中 A 是存储叶子的数组）都是叶子节点，需要检查。这意味着 8571412 次比较只是为了找到最小值。在那之后，没有简单的方法可以 'remove' 最小值而不引入不能通过简单地移动叶子来填充的间隙。
这是一个印刷错误。也许老师想问 removeMax，答案接近 50 -- 见下文：
由于每个节点有 7 个子节点，heapify 对每个级别进行了 7 次比较。如果 h 是堆的高度，那么就是 7*h 比较。
粗略分析：（这里~的意思是大概） h ~ log_7(10^6) = 7.1，因此总比较 7*7.1 ~ 50
更准确的分析： 一个 7 元堆将包含以下元素：1 + 7 + 7^2 + ... + 7^h = 10^6
左边是一个几何级数，总和为：(7^h -1)/6 = 10^6
=> 7^h = 6*10^6 + 1 => h = lg_7(6*10^6 + 1) = 8 (approximately) ，因此 7*8 = 56，仍然来自选项 50 是最接近的。
*A 是排序堆的数组。