[理工] binomial heap vs fibonacci heap

楼主: waterman815   2015-01-23 18:04:56
如题as title
这两种资料结构总是搞得不清不楚QQ
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)
作者: kather (Kather)   2015-01-23 18:09:00
bp merge是O(1)bp insert不用分摊就是O(1)bp=binomial heap 应该要打bh = =
作者: victor801120 (说好要11点睡的)   2015-01-23 20:40:00
堆积的选择,好像就是看你的算法比较常使用哪些操作?像算法课本上说Prim算法用二元堆积需要O( E*lgV),但用费式堆积会提升到O( E+ V*lgV )。觉得搞糊涂+1
作者: galapous (墨)   2015-01-23 22:52:00
merge不是O(log n)吗@@ 
作者: a95641126 (勋哥)   2015-01-24 11:05:00
不是prim把是kruskal吧
作者: galapous (墨)   2015-01-26 15:44:00
是prim喔

Links booklink

Contact Us: admin [ a t ] ucptt.com