binary-tree - 将元素插入二进制最小堆

Question

如果我将项目:10,12,14,1,6 一个接一个地插入到二进制最小堆中，结果会是什么样子，我的问题在于以下内容

当我开始时，我有:

10

然后

   10
  /
 12

然后

   10
  /  \
 12  14

然后

   1
  / \
 10 14
 /
12

但这不对，那么正确的方法是什么？

注意:这是一个家庭作业问题，我试图理解这个概念，如果你觉得解决这个问题不舒服(这不是完整的问题)，请提供一个类似问题的例子。

Answer 1

您必须将新元素作为子元素(或完全叶)添加到堆中(而不是根)，这意味着您将它放在第一个“正确”的空闲位置(或在您的堆数组中，就在最后) .

然后你必须重新建立堆条件，这被称为“heapify”。这发生在两个阶段:

重复交换新元素(一般:违反堆条件的元素)与其父节点，只要它小于父节点并且不是根。

反复将新元素与值最小的子元素交换，直到新元素变成叶子或两个子节点都大于元素本身。

这意味着

   10
  /  \
12    14

+ 1 导致

    10
   /  \
 12    14
 /
1

这违反了堆条件，所以你必须堆

    10
   /  \
  1   14
 /
12

但这仍然不对，所以你必须再次堆肥

     1
   /  \
 10   14
 /
12

你在那里......现在一切都好:-)