插入元素二進制最小堆

Question

如果我插入的項目：陸續10,12,14,1,6成二進制最小堆一個項目怎麼會結果的樣子，我的問題是與以下

當我開始我有：

10 

然後

10 
/
12 

然後

10 
/\ 
12 14 

然後

1 
/\ 
10 14 
/
12 

，但這是不正確的，那麼什麼是這樣做的正確方法？

注：這是一個家庭作業的問題，我試圖理解這個概念，如果你不舒服解決的問題（這是無論如何也全部問題），請提供類似的問題的例子。

Answer 1

您必須將新元素添加爲子（或精確葉）到堆（不是root），這意味着你把它放在第一個「正確的」自由點（或在您的堆陣，只是最後）。

然後你必須重新建立堆條件，這就是所謂的「heapify」。這發生在兩個階段：

1. 重複交換新元素（通常：違反堆條件的元素）與其父節點，只要它小於父，並且它不是根。
2. 反覆交換具有最小值的子元素的新元素，直到新元素變爲假或兩個子節點都比元素本身大。

這意味着

10 
/\ 
12 14 

+ 1會

10 
/\ 
12 14 
/
1 

而這違反了一堆條件，所以你必須heapify

10 
/\ 
    1 14 
/
12 

但這仍然不對，所以你必須再次heapify

 1 
/\ 
10 14 
/
12 

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

Answer 2

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