[理工] 中山 104 資結 F-heap

看板Grad-ProbAsk作者 (一顆星5566)時間9年前 (2017/02/02 15:38), 編輯推噓1(1推 0噓 11→)
留言12則, 3人參與, 最新討論串1/1
http://i.imgur.com/TvLltYr.jpg
想問第四題的F heap 有人跟F heap比較熟的嗎？ 這題該怎麼作啊？ 感謝 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.72.5.2 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1486021136.A.0CF.html
→
02/02 15:50, , 1F
把48降為17後，發現比他的parent小，直接把17移出來
02/02 15:50, 1F
→
02/02 15:51, , 2F
變成另外一個子樹
02/02 15:51, 2F
→
02/02 15:51, , 3F
把37降為7後，發現比他的parent小，直接把7移出來
02/02 15:51, 3F
→
02/02 15:51, , 4F
變成另外一個子樹
02/02 15:51, 4F
→
02/02 15:52, , 5F
阿這樣就不是Fibonacci heap了耶！沒錯，正常的
02/02 15:52, 5F
→
02/02 15:54, , 6F
記得這些樹要按照root的大小排序
02/02 15:54, 6F
→
02/02 16:13, , 7F
所以這題沒有csscading cut嗎？
02/02 16:13, 7F
推
02/02 16:29, , 8F
Fibonacci heap應該直接拉出來即可，會有個指標指著
02/02 16:29, 8F
→
02/02 16:29, , 9F
min 不用照root大小排否則decrease key的時間可能
02/02 16:29, 9F
→
02/02 16:29, , 10F
不是O(1)@@ 兩個父點不同，所以沒有cascading cut
02/02 16:29, 10F
→
02/02 16:35, , 11F
喔喔對，應該是只要注意min會不會變就好，不用排序
02/02 16:35, 11F
→
02/02 16:36, , 12F
感謝更正
02/02 16:36, 12F
‣ 更多 Astar5566 的文章
文章代碼(AID): #1Oak8G3F (Grad-ProbAsk)