自下而上的构造堆

Question

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

问题是我得到这个结果：（

例如使用 'a'）

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

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

Answer 1

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

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

对于自下而上的构造，您不需要过多考虑堆的数量。基本思想是

1. 没有子节点的节点是平凡的堆。
2. 如果一个节点有两个堆作为子节点，我们可以通过冒泡操作将其转换为更大的堆。

所以一开始我们知道第 4 层（8、9 和 10）中的节点已经是堆。然后我们可以用它来冒泡第三层中的节点，将它们也变成堆，依此类推。