algorithm - 如何删除(最小)堆中的最后一个节点？

Question

我正在为考试而学习，目前我正忙得不可开交。我已经了解如何从堆中删除节点，但我可以找到无法使用该算法删除的情况。

问题是我想删除15，它是一个叶节点，也是最小堆的最后一个节点。当您删除堆中的一个节点时，您正在寻找堆的最后一个节点，将其替换为删除节点并检查该节点的子节点是否大于它..然后递归继续。

由于这个原因(15 是最后一个元素并且没有子元素)，我不知道如何删除它。

        1
     /     \
    9       6
   / \     /
 17  11   8
 /
15

我认为您可以直接删除它而无需执行任何其他操作。你基本上自己替换它，因为删除节点 = 最后一个节点..？所以它看起来像这样:

        1
     /     \
    9       6
   / \     /
 17  11   8

我希望你能帮助我，我真的需要知道我的考试，但我在互联网上找不到任何关于那个案例的信息。

Answer 1

移除最后一个节点是非常简单的任务——只需移除它，无需做更多事情(除了递减计数器和调整数组大小(如果需要)。一般情况下，函数交换 item 本身不会改变任何东西(虽然完成了无用的工作)，但您可以检查 item 是否是最后一个并省略交换。

请注意，删除非头部元素是很少见的问题(您必须提供对它的显式访问)，大多数算法只使​​用最顶层的元素。

另请注意，您的图片未显示有效的二叉堆，因为堆是完整二叉树，并且所有级别(最后一层除外)都必须完全填充，但您的树中有空位第三行。