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

Question

我正在看这个挑战：

Consider the min-heap [15, 27, 33, 39, 66, 39, 47, 58, 51], built by repeatedly inserting values into an empty heap. Which element could not have been the last element inserted into this heap?

我知道一个元素是从叶子插入的，但是那个叶子元素根据它的值来定位，这让我很困惑。

我做了对应的二叉树：

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

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 中的任何一个，此“问题”都不会出现在示例树中：它们都小于它们的兄弟姐妹（如果它们有的话）。

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

Find the last element inserted into the min heap?

arrays

data-structures

binary-tree

heap

heapsort

一点警告