在堆排序中插入/删除相同的元素

Question

按以下顺序将以下数字插入最初为空的最小堆时，在每个阶段显示堆：{11, 17, 13, 4, 4, 1 }。现在，当我们连续对堆执行deleteMin操作直到其为空时，显示每个阶段的堆。

这是我收到的答案/检查点：

![1]https://imgur.com/zu47RIF

我有两个问题，请：

1. 我不知道何时第二次插入元素4，为什么我们要移动11使其成为旧元素/首次插入的元素4的右子元素？是否因为我们要满足完整二叉树的要求，即从1到k - 2级别中的每个节点正好有2个子节点（k =树的级别，级别k是最底层的级别） ）？

2. 我不知道我们如何deleteMin = 1，13成为新父项11的右孩子（这是4的左孩子）。请注意，我的老师给了全班2种deleteMin方法。另一种方式对我来说很好-这只是插入的相反过程。

Answer 1

1. 就像您说的那样，堆形状是“几乎完整的树”：所有级别都是完整的，除了最低级别可能在右侧不完整。因此，第二个4必须添加到17的右侧以保留堆的形状：

        4
      /   \
    11     13
  /    \
17      4

之后，4用11切换位置以重新获得min-heap属性。

2. 删除通常是通过删除根并将最后一个元素（即最右下角）放在其位置来实现的。这样可以保留堆的形状。然后允许新的根向下筛选以重新获得min-heap属性。因此，13成为新的根：

        13
      /    \
    4       4
  /   \
17     11

然后13用任一子节点切换位置。看起来他们在您的示例中选择了合适的孩子。