将元素插入二进制最小堆

Question

如果我插入项目:10,12,14,1,6到二进制最小堆一个项目接一个怎么样的结果,我的问题是以下

当我开始时我有:

10

然后

   10
  /
 12

然后

   10
  /  \
 12  14

然后

   1
  / \
 10 14
 /
12

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

注意:这是一个功课问题,我试图理解这个概念,如果你觉得不能解决问题(这不是完整的问题)请提供一个类似问题的例子.

Answer 1

你必须将新元素作为子元素(或者确切地说是叶子)添加到堆中(而不是作为根),这意味着你将它放在第一个"正确"的空闲点(或者在你的堆数组中,就在最后) .

然后你必须重新建立堆条件,这称为"heapify".这分两个阶段发生:

1. 重复交换新元素(一般:违反堆条件的元素)与其父节点,只要它小于父节点并且它不是根节点.
2. 重复地将新元素与具有最小值的子元素交换,直到新元素变为离开或两个子节点都大于元素本身.

这意味着

   10
  /  \
12    14

+ 1导致

    10
   /  \
 12    14
 /
1

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

    10
   /  \
  1   14
 /
12

但这仍然不对,所以你必须再次堆积

     1
   /  \
 10   14
 /
12

你有...现在一切都好了:-)