作者joywilliamjo (joywilliamjoy)
看板Grad-ProbAsk
標題[理工] 106 台大電機丙 資結
時間Mon Dec 7 18:58:30 2020
第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://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1607338712.A.403.html
1F：→ mathtsai: 找max要遍歷整個heap才能找到12/07 19:41
2F：推 hero97212: 12答案應該是D E12/07 23:21
好的謝謝
3F：→ hero97212: B 用 aggregate method 結果會是O(N)12/07 23:22
4F：→ hero97212: C的話舉個反例就好12/07 23:23
這個目前想到就是直接變大於K+1這樣
5F：→ aa871220: Heap 一定是complete tree12/08 10:29
6F：→ aa871220: 而最大值一定在最底層12/08 10:29
7F：→ aa871220: 一定要traverse過整個leaf node12/08 10:29
8F：→ aa871220: 其最多會有n/2個node 故為O(N)12/08 10:29
了解
感謝
※ 編輯: joywilliamjo (42.74.26.5 臺灣), 12/08/2020 16:50:18