[理工] 資結 Fibonacci heap delete x

看板Grad-ProbAsk作者 (chiu)時間5年前 (2018/10/31 15:46), 編輯推噓1(1推 0噓 4→)
留言5則, 2人參與, 5年前最新討論串1/1
http://i.imgur.com/1LC1I8a.jpg
關於delete x的時間 查了一下之後的理解是 因為要先decrease到最小再delete-min 所以是O(log n) (delete-min時merge的時間) 但是筆記下方又寫如果不是min的話採lazy merge 這樣為什麼還需要O(log n)呢? 謝謝各位～ ----- Sent from JPTT on my HTC_D830x. -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 39.8.34.253 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1540971962.A.757.html
推
10/31 16:50, 5年前 , 1F
所以按照你的說法，取兩個case比較久的那個，就還
10/31 16:50, 1F
→
10/31 16:50, 5年前 , 2F
是O(lgn)阿，這是複雜度定義
10/31 16:50, 2F
→
10/31 21:43, 5年前 , 3F
了解～還有一個問題就是delete x到底需不需要merge到不
10/31 21:43, 3F
→
10/31 21:43, 5年前 , 4F
同高度 還是lazy就好？因為查到的是不管是刪最小或任意
10/31 21:43, 4F
→
10/31 21:43, 5年前 , 5F
數都還是會做到delete-min 這個動作 那不就不lazy了嗎
10/31 21:43, 5F
‣ 更多 q5332159 的文章
文章代碼(AID): #1RsLswTN (Grad-ProbAsk)