java - 从二进制最大堆中删除根节点的算法

Question

我坐在这里研究一种算法，用于删除二进制最大堆中的根节点，然后用新根更新树。这是它的样子:

if (n==0) {
  empty = true;
} else {
  empty = false;
  top = a[1];
  a[1] = a[n];
  n = n-1;
  parent = 1;
  child = 2;

  while (child<=n-1) {
    if (tab[child]<tab[child+1]){
      child = child+1;
    }
    if (tab[child]>tab[parent]) {
      swap[tab[child],tab[parent]);
      parent=child;
      child=parent*2;
    } else {
      child=n;
    }
  }
}

所以，我不明白的是为什么它说:

while(child<=n-1)

我的意思是，假设我们有一个包含 11 个节点的堆，包括根节点。当我们删除根节点时，我们剩下 10 个节点。根据这段代码，如果 child = 10，循环应该停止。但这有什么意义呢？即使 child = 10 和 parent = 5，它不应该仍然运行 if 来查看 child > parent 吗？为什么它不检查那个场景，而是停止循环？

希望这是有道理的。很抱歉，如果这很明显，我整天都在查看堆和节点，但我的头脑不再合作了。

Answer 1

您必须检查两个子节点。从二进制最大堆中移除的规则是:

1. 结果是堆顶部的节点(即根节点)。
2. 将项目从堆尾移到堆顶。
3. 当您插入的项目小于其最大的子项时，将其与最大的子项交换。

您的代码没有正确执行第 3 步。您首先必须确定哪个是最大的 child 。

我怀疑代码使用了 (child <= n-1)因为它假定您将检查 child 处的项目和 child+1以满足第3步的要求。

修改帖子后添加

我认为 (child <= n-1)是一个错误。应该是:

while (child <= n)
{
    if (child < n && tab[child] < tab[child+1])
    {
        child = child+1;
    }

否则如你所说，有可能无法进行比较。