[理工] [DS]-台大95-資工所

[assassin88 (AI)]

《資料結構》 洪逸 P.9-74
Which of the following is true about the heap data structure ? n is node num.

(a)Deleting the minimum element in a min-heap takes O(logn) time
(b)Finding the minimum element in a min-heap takes O(logn) time
(c)Inserting a node into a Fin. heap takes O(logn) time
(d)Decrease-key operation on a node of a Fib. heap takes O(1) time
(e)Finding both the monimum and the maximum elements in a min-max heap
   takes O(1) time

答案是給(A)(C)(D)(E)，
可是我覺得答案有點問題，
(B)應該是O(1)
(C)應該是O(1)
(D)應該是O(logn)
答案是(A)(E)？

請指教..感謝

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.57.78.8
※ 編輯: assassin88      來自: 61.57.78.8           (01/15 00:25)
推 extremity:c的fin是？fib的話，insert是O(1)沒錯
→ extremity:decrease key也是O(1)，可用Amortize證
→ assassin88:C打錯..是Fib. 沒錯~所以C是錯的?
→ assassin88:請問Amortize證明哪邊有提到??
推 supergud:(C)in wrost case是O(logn) 大部分case和avg.才是O(1)
→ supergud:題目沒說是一般情形 所以有可能是worst case