如何从Max-Heap中删除？

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交换。

编辑:因为我们总是与较大的子级交换，所以它确保我们最终得到一个有效的堆(例如，如果我们用55而不是70交换我们的15，我们将70作为55的子级，这是不好的)

Answer 3

为了加法，你把新的值放在最后(在你的例子中是20 )，然后你尝试修复堆，也就是将它与他的父级进行比较，如果它大于交换，再比较一次，直到不需要交换(或者你到达根)

为了删除，你需要替换最后一个对象(在你的例子中是15)，并向下修复堆。