作者k1006boy (@@)
看板Prob_Solve
标题[问题] heapify worst case
时间Mon Oct 5 12:35:35 2009
我看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)
1F：→ k1006boy:没记错是在p.131 10/05 12:48
2F：推 raincole:两个子树为高度差1的全满二元树，则高的有2x个节点 10/05 19:45
3F：→ raincole:低的有x个 故高子树节点数为整体节点数的2/3（2x/3x） 10/05 19:46
4F：→ raincole:我描述能力有点差 你画一个有9个节点的binary heap 10/05 19:49
5F：→ raincole:就会知道书中那段的意思了 10/05 19:49