[問題] heapify worst case

看板Prob_Solve作者 (@@)時間16年前 (2009/10/05 12:35), 編輯推噓1(1推 0噓 4→)
留言5則, 2人參與, 最新討論串1/1
我看Introduction to algorithms 在分析MAX-heapify T(n) = T(2n/3) + O(1) 有一句話是這樣說的 the children's subtrees each have size at most 2n/3 the worst case occurs when the last level of the tree is exactly half full 我是想問 2n/3是如何求得的? 那本書那一段話怎麼看我都看不懂@@ 謝謝了.. -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.123.104.24 ※ 編輯: k1006boy 來自: 140.123.104.24 (10/05 12:45) ※ 編輯: k1006boy 來自: 140.123.104.24 (10/05 12:47) ※ 編輯: k1006boy 來自: 140.123.104.24 (10/05 12:47)
→
10/05 12:48, , 1F
沒記錯是在p.131
10/05 12:48, 1F
推
10/05 19:45, , 2F
兩個子樹為高度差1的全滿二元樹，則高的有2x個節點
10/05 19:45, 2F
→
10/05 19:46, , 3F
低的有x個 故高子樹節點數為整體節點數的2/3（2x/3x）
10/05 19:46, 3F
→
10/05 19:49, , 4F
我描述能力有點差 你畫一個有9個節點的binary heap
10/05 19:49, 4F
→
10/05 19:49, , 5F
就會知道書中那段的意思了
10/05 19:49, 5F
‣ 更多 k1006boy 的文章
文章代碼(AID): #1AoNUOww (Prob_Solve)