如何删除（min-）堆中的最后一个节点？

Question

我正在学习考试，目前我在堆。我已经理解如何从一个堆中删除一个节点，但是我可以找到一个我不能使用该算法删除的情况。

问题是我想删除15这是一个叶子和最小堆的最后一个节点。当您删除堆中的节点时，您正在查找堆的最后一个节点，将其替换为删除节点，并检查此节点的子节点是否大于此节点..然后以递归方式继续此操作。

因此（15是最后一个元素，没有孩子），我不知道如何删除它。

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

我认为你可以删除它，而无需执行其他任何操作。由于删除节点=最后一个节点，所以基本上可以自行替换它。因此，它看起来像这样：

 1 
    / \ 
    9  6 
/\ /
17 11 8 

我希望你能帮助我，我真的需要知道我的考试，我找不到任何有关在互联网上这种情况下，任何东西。

Answer 1

删除最后一个节点是非常简单的任务 - 只是删除它，没有什么可做的（除非递减计数器并在需要时调整数组大小）。一般情况下，功能交换项目本身并不会改变（虽然无用的工作完成），但您可以检查项目是否是最后一个，并省略交换。

请注意，删除非头元素是罕见的问题（您必须提供明确的访问权限），大多数算法只使​​用最顶层的元素。

另请注意，您的图片没有显示正确二进制堆，因为堆是完整二叉树，和所有级别（除最后一个）必须完全充满，但你的树有第三排的空位子。