javascript - 二叉堆 - 为什么删除函数需要调用 bubbleUp 方法？

Question

我一直在通过 eloquentjavascript 网站学习 JavaScript，并得到了一些我似乎无法理解的代码:

remove: function(node) {
    var length = this.content.length;
    // To remove a value, we must search through the array to find
    // it.
    for (var i = 0; i < length; i++) {
      if (this.content[i] != node) continue;
      // When it is found, the process seen in 'pop' is repeated
      // to fill up the hole.
      var end = this.content.pop();
      // If the element we popped was the one we needed to remove,
      // we're done.
      if (i == length - 1) break;
      // Otherwise, we replace the removed element with the popped
      // one, and allow it to float up or sink down as appropriate.
      this.content[i] = end;
      this.bubbleUp(i);
      this.sinkDown(i);
      break;
    }
  },

我的问题是 - 为什么这个函数需要调用 bubbleUp()？ 如果 end 是二叉堆上的最后一个值，并且每个推送到堆上的值在通过 push() 方法添加时都会调用 bubbleUp，那么 end 值的分数怎么可能比 i 处的值低呢？我对数据结构很陌生，似乎无法弄清楚这一点。

Answer 1

想象一个像这样的最小堆:

       1
   10      2
 18  20  3   4

现在，假设您删除了 20。您的代码基本上将 4 固定在其位置。

       1
   10      2
 18   4  3

由于 4 < 10，它必须冒泡才能满足最小堆的要求。