插入元素二进制最小堆

如果我插入的项目：陆续10,12,14,1,6成二进制最小堆一个项目怎么会结果的样子，我的问题是与以下插入元素二进制最小堆

当我开始我有：

然后

10 
/
12

然后

10 
/\ 
12 14

然后

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

注：这是一个家庭作业的问题，我试图理解这个概念，如果你不舒服解决的问题（这是无论如何也全部问题），请提供类似的问题的例子。

来源

2010-01-19 user220755

您必须将新元素添加为子（或精确叶）到堆（不是root），这意味着你把它放在第一个“正确的”自由点（或在您的堆阵，只是最后）。

然后你必须重新建立堆条件，这就是所谓的“heapify”。这发生在两个阶段：

重复交换新元素（通常：违反堆条件的元素）与其父节点，只要它小于父，并且它不是根。
反复交换具有最小值的子元素的新元素，直到新元素变为假或两个子节点都比元素本身大。

这意味着

10 
/\ 
12 14

+ 1会

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

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

你瞧......一切就OK了，现在:-)

来源

2010-01-19 12:10:03 Leo

但14比12以上，这是怎么下令？ – user220755 2010-01-19 12:20:03

这并不违反堆条件......看看http://upload.wikimedia.org/wikipedia/commons/6/69/Min-heap.png 36大于19,7大于2等等 – Leo 2010-01-19 12:25:48

或者澄清一下：你的解决方案是正确的！我只是解释了如何到达算法... – Leo 2010-01-19 12:32:27

step1:  10 
step2:  10 
     /
     12 
step3:  10 
     /\ 
     12 14 
step4:  1 
     /\ 
     10 12 
     /
     14 
step5:  1 
     /\ 
     6 10 
     /\ 
     12 14

来源

2012-01-13 23:59:34 Fred

插入元素二进制最小堆

回答

相关问题