问自下而上的构造堆
EN

Stack Overflow用户

提问于 2011-11-11 07:44:07

回答 1查看 6.2K关注 0票数 1

我正在做一个问题，我有10个键，我必须做一个自下而上的构造。根据我的书，我应该构造(n+1)/2堆，即11/2=5.5堆的底部。然后第二层是11/4，第三层是11/8，依此类推。

问题是我得到的结果是：

(例如使用'a‘)

由于11/2=5.5，所以我舍入为6，11/4=2.75so 3，11/8=1.375 so 2，11/16=0.6875 so 1。

即使我不四舍五入，我仍然有一堆奇怪的东西。有人能解释一下我哪里搞砸了吗？

回答已采纳

发布于 2011-11-11 08:08:39

你搞砸了，因为只允许二进制堆中的最后一层不满。包含10个元素的堆应该如下所示：

        1
     /     \
    2       3
   /  \    / \
  4    5  6   7
 /\   /
8  9  10

至于自下而上的结构，你不需要过多地考虑堆的数量。基本的想法是

没有子节点的

所以一开始我们就知道第四层(8，9和10)中的节点已经是堆了。然后，我们可以使用它来冒泡第三层中的节点，将它们转换为堆，依此类推。

票数 1

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/8087965

复制

相似问题

问自下而上的构造堆EN