如何向下堆？

Question

我目前正在做一个数据结构和算法类的作业。

我必须从给定的堆中删除节点；

         6     after replacing the node ;            20  
       /   \                                        /  \
     11     9                                      11    9
    /  \   / \                                    / \   / \
   17  18 15 10                                  17 18 15 10
  /
 20

我的问题是，我是向右下堆，还是向左下堆，还是有关系？

Answer 1

因为你在那里有一个最小堆，你的下堆操作应该用它的较小的子级交换新的父级。否则，您的交换可能会导致违反堆条件。

Answer 2

您需要将父节点与具有较小值的子节点进行交换，并且此过程需要继续，直到满足堆的基本条件