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

看板Grad-ProbAsk作者 (joywilliamjoy)時間3年前 (2020/12/07 18:58), 3年前編輯推噓1(1推 0噓 7→)
留言8則, 3人參與, 3年前最新討論串1/1
第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
→
12/07 19:41, 3年前 , 1F
找max要遍歷整個heap才能找到
12/07 19:41, 1F
推
12/07 23:21, 3年前 , 2F
12答案應該是D E
12/07 23:21, 2F
好的謝謝
→
12/07 23:22, 3年前 , 3F
B 用 aggregate method 結果會是O(N)
12/07 23:22, 3F
→
12/07 23:23, 3年前 , 4F
C的話舉個反例就好
12/07 23:23, 4F
這個目前想到就是直接變大於K+1這樣
→
12/08 10:29, 3年前 , 5F
Heap 一定是complete tree
12/08 10:29, 5F
→
12/08 10:29, 3年前 , 6F
而最大值一定在最底層
12/08 10:29, 6F
→
12/08 10:29, 3年前 , 7F
一定要traverse過整個leaf node
12/08 10:29, 7F
→
12/08 10:29, 3年前 , 8F
其最多會有n/2個node 故為O(N)
12/08 10:29, 8F
了解 感謝 ※ 編輯: joywilliamjo (42.74.26.5 臺灣), 12/08/2020 16:50:18
‣ 更多 joywilliamjo 的文章
文章代碼(AID): #1VpWhOG3 (Grad-ProbAsk)