在7进制树的最大堆中，对removeMin()的调用将进行多少比较？

Question

假设包含10^6元素的max堆存储在完整的7进制树中。对removeMin()的调用将进行多少次比较？

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

我的解决方案:比较的数量最多应该等于叶节点的数目，因为在最大堆中，最小。可以在上述选项中没有的任何叶节点上找到。更好的方法是将10^6的平方( log为10^6到基7)取为50，但这只是当我们确定最小元素将跟随一根树枝穿过树时，而在最大堆的情况下，这是不正确的。希望你能帮上忙。

Answer 1

Min元素可以是最大堆的任何叶子，也可以是任何类型，并且没有订单。从A10^6/7 +1开始的所有元素(其中A是存储叶子的数组)都是叶节点，需要检查。这意味着要进行8571412次比较，以求最小值。在此之后，没有简单的方法“移除”最小值，而不引入一个不能通过简单地移动树叶来填补的空白。

这是印刷错误。也许老师想问removeMax，这个问题的答案接近50 -见下文：

由于每个节点都有7个子节点，因此每个级别有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(约)，因此7*8 = 56，仍然从选项50是最近的。

*A是排序堆的数组。