找到插入最小堆的最后一个元素？

Question

我正在关注这个挑战：

考虑最小堆 [15, 27, 33, 39, 66, 39, 47, 58, 51]，它是通过将值重复插入空堆而构建的。哪个元素不可能是最后插入到该堆中的元素？

我知道一个元素是从叶子插入的，但是该叶子元素根据其值占据位置，这让我感到困惑。

我已经制作了对应的二叉树：

如何确定哪些值不能最后插入？

Answer 1

向堆中插入需要执行以下步骤：

• 将值追加到数组末尾
• 如果该值小于其父级，则将该值与其父级交换
• 对父级重复交换步骤，直到确认堆属性。

因此插入的值可能最终出现在从“最后”叶子到根的路径上的某个位置。

在这种情况下，树是：

            15
          //   \
         27     33
        // \   /  \
       39  66 39  47
      / \\
     58  51

“最后”叶子是 51，到根的路径已用双线标记。所以最后插入的候选数是 15、27、39 和 51。

例如，如果我们暂时假设 15 是最后插入的，那么在插入之前树必须是这样的（星号表示插入点）：

            27
          //   \
         39     33
        // \   /  \
       51  66 39  47
      /  
     58  *

插入的 15 将沿着双标记路径交换路径直至根。没有其他节点参与此操作。

结论： 最后无法插入的元素为：33、66、39、47、58。

一点警告

我们应该在插入之前验证树是否是一个有效的堆。上面的例子总是这样，但是如果我们对这棵树有疑问（注意底层的变化）：

            15
          //   \
         27     33
        // \   /  \
       39  66 39  47
      / \\
     51  58

...那么最后插入的唯一可能值是 58。这是因为在插入发生之前，58 不可能是 51 的父级。这将违反堆属性。因此它不能被向下交换以向上移动插入的值。 此场景的特点是路径上的值大于其直接

同级

（在此修改示例中，58 大于 51）。 但是，对于任何值 15、27、39 或 51，此“问题”不会出现在示例树中：它们都小于其同级（如果有）。