如何从最大堆中删除？

Question

如果我们将15放在根中，那么heapify的过程将是什么？

            85
            /\
           /  \
          /    \
        55      70
        /\      /\
       /  \    /  \
      22  33  30  65
     /\   /
   14 15 15

应该从堆中删除85的方法是什么？

Answer 1

由于您总是将其与两者中较大的一个交换（heap属性表示父级始终大于其子级）：

            15
            /\
           /  \
          /    \
        55      70
        /\      /\
       /  \    /  \
      22  33  30  65
     /\   
   14 15

            70
            /\
           /  \
          /    \
        55      15
        /\      /\
       /  \    /  \
      22  33  30  65
     /\   
   14 15

            70
            /\
           /  \
          /    \
        55      65
        /\      /\
       /  \    /  \
      22  33  30  15
     /\   
   14 15

Answer 2

[如果删除85，然后将其替换为15，则可以通过减堆将半堆转换回堆，即，根节点的15将沿着较大子级的路径“下沉”。在这种情况下，它将与70交换，然后与65交换。

编辑：因为我们总是与较大的子项交换，所以可以确保我们得到一个有效的堆（例如，如果将15与55而不是70交换，我们将70作为55的子项，这是不好的）

Answer 3

要添加，将新值放在最后（在本例中为20），然后尝试修复堆，即与父级进行比较，如果交换较大，则再次比较直到没有交换为止需要（否则您将成为root）

为了删除而删除，请替换最后一个对象（示例中为15）并向下固定堆。

Answer 4

要删除这里是根的85。

1. 您可以替换为最后一个叶子（15）。
2. 再次堆砌link to build heap