作者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/cn.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