作者ybite (小犬)
看板Grad-ProbAsk
標題Re: [理工] [DS]成大99-電通甲
時間Mon Feb 7 10:23:01 2011
※ 引述《aerystyle (阿che)》之銘言：
: 輸入:12.8.14.17.9.6.3.33.25.16
: 求SMMH結果?
: _
: / \
: 3 33
: / \ / \
: 6 25 8 9
: / \ / \
: 12 14 16 17
: 這是我的答案,_代表空NODE，請各位高手幫我檢查一下是否有誤，謝謝
算了，寫下來好了。
SMMH的性質：
* Root放空
* 任何一個節點的左子樹比右子樹小
* 對某個節點而言，考慮以此節點為根的子樹
根的左子樹擁有樹根所有後代中最小的值（所以不考慮樹根）
根的右子樹擁有樹根所有後代中最大的值（一樣不考慮樹根）
舉例：整顆樹的值都介於3～33，以3為根的子樹除了3以外都介於6～25。
因此在整個SMMH過程中都必須維持三個性質：
P1. 如果某個節點有兄弟，左兄弟<右兄弟
P2. 如果某個節點有祖父，祖父的左兒子<該節點
P3. 如果某個節點有祖父，祖父的右兒子>該節點
插入時：
1. 先放在整顆 Heap 中最「後面」的位置（最後一層最右邊）
2. 如果他有左兄弟而且比他大（不滿足P1），交換左右兄弟
3. 由下往上檢查新節點祖父的左兒子和祖父的右兒子
如果新節點比祖父的左兒子小（不滿足P2），兩點交換
如果新節點比祖父的右兒子大（不滿足P3），兩點交換
在同時滿足P2和P3性質過後就算插入完成
Delete-min或Delete-max：
1. 把Heap最後一層最右邊的值拿去補要刪掉的值
2. 由上而下重新檢查P2和P3性質（類似上者）
有些書/講義會特別用「E」表示要插入/遞補的新節點...
在大小檢查完之後，最後再把E填上數字，這種表記方式好像還蠻常見的？
ok，所以原題是要輸入:12.8.14.17.9.6.3.33.25.16
插入12
_
/
12
插入8，此時違反P1規則，交換左右：
_ -
/ \ → / \
12 8 8 12
插入14，但此時14比12更大，交換：
_ -
/ \ / \
8 12 → 8 14
/ /
14 12
插入17，此時17比14還大，交換：
_ -
/ \ / \
8 14 → 8 17
/ \ / \
12
17 12 14
插入9，由於9位在8～17之間，沒問題：
_
/ \
8 17
/ \ /
12 14
9
插入6，首先由於左兄弟比較大，交換左右：
然後因為6比8還要小，因此交換:
_ _ _
/ \ / \ / \
8 17 →
8 17 → 6 17
/ \ / \ / \ / \ / \ / \
12 14
9 6 12 14
6 9 12 14 8 9
插入3：此時3比12還小，交換
再往上一層後，3還是比6小，再換：
_ _ _
/ \ / \ / \
6 17 →
6 17 → 3 17
/ \ / \ / \ / \ / \ / \
12 14 8 9
3 14 8 9 6 14 8 9
/ / /
3 12 12
插入33：此時33比14還大，交換
再往上一層後，33還是比17大，再換：
_ _ _
/ \ / \ / \
3 17 →
3 17 → 3 33
/ \ / \ / \ / \ / \ / \
6 14 8 9 6
33 8 9 6 17 8 9
/ \ / \ / \
12
33 12 14 12 14
插入25：25比17大，交換。交換之後25位在3～33之間，沒問題！
_ _
/ \ / \
3 33
3 33
/ \ / \ → / \ / \
6 17 8 9 6
25 8 9
/ \ / / \ /
12 14
25 12 14 17
插入16：左兄弟比他大，左右交換。
_
/ \
3 33
/ \ / \
6 25 8 9
/ \ / \
12 14
17 16
交換過後16位在6～25之間，沒問題！因此做完就是這樣：
_
/ \
3 33
/ \ / \
6 25 8 9
/ \ / \
12 14 16 17
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 122.127.180.129
推 max1147:認真推一個 02/07 11:24
推 qqoil:寫得很詳細 02/07 11:59
推 jimmy90332:詳細推!!! 02/07 12:09
推 koehie:Thanks. 02/07 15:37
推 dy957:感恩! 02/07 23:06
推 skill91002:大推用心!!!!!!!! 02/07 23:27
推 willne:只有感謝! 02/07 23:36
→ jerryhu2:3Q 02/09 00:19
推 starkers:佛心推!! 02/23 19:18
推 iamjustakid:推! 02/25 21:58
推 a1098137129:推 12/29 00:17
推 arcticocean:寫的超清楚 感謝你！ 01/09 19:55