假设一个 最大堆积 10^6个元素存储在一个 七叶树. 大约有多少人 比较 呼吁 removeMin() 将使?
我的解决方案。 比较的数量最多应该等于叶子节点的数量，因为在max堆中，最小元素可以在任何一个叶子节点上找到，而这在上述选项中是没有的。更好的方法是取（10^6的对数到7的基数）的平方，这给出了50，但这只是当我们确定最小元素将遵循一个单一的分支跨树的情况下，在最大堆的情况下是不正确的.我希望你能帮助。
没有 "自然 "的方法可以从max堆中删除最小值。你只需要查看所有的叶子节点，找出哪个节点恰好是最小值。
那么问题是有多少个叶子节点。直觉上，我们会期望堆中叶子节点的分数与总节点数相当接近。把它带到极限--如果你有一个1,000,000-ary堆，你会在顶层有一个节点，而所有剩余的999,999个元素在下一层。即使在最小的情况下，堆是一个二进制堆，你也会期望大约有一半的元素在底层。
更具体地说，我们来算一算! 一个有n个节点的7ary堆会有多少叶子? 好吧，树上的每个节点要么是
有一个可能的例外，那就是由于最底层的一行可能并不满，所以可能有一个节点的子节点少于七个。由于这只是一次性的，所以当我们处理数百万个元素时，我们可以忽略最后一个节点。可以用归纳法快速证明，任何一棵树，每个节点要么没有子节点，要么有7个子节点，叶子节点的数量是内部节点的7倍（证明这个！），所以我们会期望比（78）ths的节点是叶子，总共要检查875000个叶子。
因此，这里的最佳答案大概是106 的比较。
最小元素可以是max堆的任何一个叶子，也可以是任何类型，那里没有顺序。从A[10^67+1]开始的所有元素（其中A是存储叶子的数组）都是叶子节点，需要检查。这意味着仅仅为了找到最小值，就要进行8571412次比较。在这之后，没有简单的方法来 "删除 "最小值，而不引入一个不能通过简单移动叶子来填补的空白。
这是一个错误的印刷。也许老师想问的是removeMax，对于这个问题，答案接近50--见下文。
因为每个节点有7个子节点，所以堆化每层有7次比较。如果h是堆的高度，那么就是7*h次比较。
粗略分析一下。(这里~指的是大概)h~log_7(10^6)=7.1，因此总的比较次数为7*7.1~50次。
更准确的分析:一个7-ary堆会有元素。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是数组，用于排序堆。