[理工] 106 台大電機丙 資結

[joywilliamjo (joywilliamjoy)]

第9題
https://i.imgur.com/1ArbQc2.jpg
如果是min heap的話找min在O(1)但找max不是O(logn)嗎？

然後是第12題
搜過版上的答案似乎有點多元...
https://i.imgur.com/Vy2CuCr.jpg
https://i.imgur.com/3PKwaf8.jpg
想問一下C錯的地方以及這題的答案
C錯是因為應該是（k+1)嗎？



--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.74.26.5 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1607338712.A.403.html
→ mathtsai: 找max要遍歷整個heap才能找到
推 hero97212: 12答案應該是D E
好的謝謝
→ hero97212: B 用 aggregate method 結果會是O(N)
→ hero97212: C的話舉個反例就好
這個目前想到就是直接變大於K+1這樣
→ aa871220: Heap 一定是complete tree
→ aa871220: 而最大值一定在最底層
→ aa871220: 一定要traverse過整個leaf node
→ aa871220: 其最多會有n/2個node 故為O(N)
了解
感謝
※ 編輯: joywilliamjo (42.74.26.5 臺灣), 12/08/2020 16:50:18