Insert/remove堆排序中的相同元素

Insert/remove the same element in heap sort

当以下数字按给定顺序插入初始为空的 min-heap 时，显示每个阶段的堆：{11, 17, 13, 4, 4, 1 }。现在，展示一下我们在堆上连续执行deleteMin操作直到堆为空时，各个阶段的堆。

这是我收到的answer/checkpoint：

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

请问我有2个问题：

  1. 不明白，第二次插入元素4时，为什么要shift 11，使之成为旧的右边的child element/firstly 插入元素 4？是不是因为我们要满足一个完全二叉树的要求，就是1到k - 2层的每个节点正好有2children（k=树的层数, k级为bottom-most级)?

  2. 不明白我们deleteMin = 1,13怎么变成新parent11的右边child(这是 4 的左边 child）。快速说明一下，我的讲师给出了 class 2 种 deleteMin 方法。另一种方式对我来说很好 - 它只是插入的相反过程。

  1. 就像你说的，堆的形状是"almost complete tree"：所有层次都完整，除了最右边的层次可能不完整。因此，第二个4必然要加在17的右边，以保持堆形：
        4
      /   \
    11     13
  /    \
17      4

之后，4与11互换位置，夺回min-heap属性。

  1. 删除通常是通过删除根并将最后一个（即 bottom-rightmost）元素放在原处来实现的。这保留了堆的形状。然后允许新根向下筛选以重新获得 min-heap 属性。所以 13 成为新的根：
        13
      /    \
    4       4
  /   \
17     11

然后 13 与任一 child 节点交换位置。看起来他们在您的示例中选择了 right-hand child。