[理工] binomial heap vs fibonacci heap

[waterman815 ()]

如題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: bp merge是O(1)
→ kather: bp insert不用分攤就是O(1)
→ kather: bp=binomial heap 應該要打bh = =
推 victor801120: 堆積的選擇，好像就是看你的演算法比較常使用哪些
→ victor801120: 操作？
推 victor801120: 像演算法課本上說Prim演算法用二元堆積需要O( E*lgV
→ victor801120:  )，但用費式堆積會提升到O( E+ V*lgV )。
→ victor801120: 覺得搞糊塗+1
推 galapous: merge不是O(log n)嗎＠＠　
推 a95641126: 不是prim把是kruskal吧
推 galapous: 是prim喔