[理工] binomial heap vs fibonacci heap

看板Grad-ProbAsk作者waterman815時間11年前 (2015/01/23 18:05)推噓5(5推 0噓 6→)

留言11則, 4人參與討論串1/1

如題as title 這兩種資料結構總是搞得不清不楚ＱＱ google一些資料看了一些書也翻了洪兔的筆記發現有些東西寫的不太一樣想要求解（時間複雜度有些是用分攤成本有些是用平均成本）自己做了一些小小統整但不確定是否正確想請版上的大大指教一下 *Binomial heap 提供的服務 & time complexity merge O(logn) delete-min O(logn) find-min O(logn) insert x O(1) （分攤成本） *Fibonacci heap 提供的服務 & time complexity 有看蔡欣穆老師的投影片特別強調一點「除了delete min」其他都可達到O(1) merge O(1) ---直接把tree合併起來 delete-min O(logn) find-min O(1) insert x O(1) ---放入forest中不需同高度合併把所有事情放到之後再做新增了 delete x O(logn) 因為delte x是將x當成是-無限大再將其做delete min decrease key O(1) 另外想要問 fibonacci heap是否不需要要求和binomial一樣的製作特性例如B3 node數= 2^3這種特性還有想要知道 fibonacci heap 以及 binomial heap 的主要應用會用在什麼地方？？搞得有點糊塗想詢問版上的大大謝謝 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.119.120.6 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1422007501.A.AED.html

→

kather

01/23 18:09, , 1^F

01/23 18:09, 1^F

→

kather

01/23 18:10, , 2^F

01/23 18:10, 2^F

→

kather

01/23 18:14, , 3^F

01/23 18:14, 3^F