推 hirabbitt:感恩 03/06 23:21
※ 引述《hirabbitt (兔子)》之銘言：
: 請問關於費氏堆積
: 哪邊有資料可以看?
: 我的這本好像沒有提到
: 然後網路資料都好像已經當做大家都懂了
: 還是可以請板友幫忙解釋一下>.<
: 謝謝
你先去搞懂binary max/min heap，然後binomial heap，最後才是Fibonacci heap。
可以參考Introduction to Algorithm chapter 6,19,20!!
從binary heap開始討論。
把兩個binary heap做union(就是把兩個資料結構合起來)的時間比較久(O(n))。
所以想要發展一種做union比較快的資料結構，於是有了binomial heap。
可是binomial heap會導致一些operations速度下降(例如找最小值)。
所以進而發展了Fibonacci heap。
在理論上，Fibonacci heap的速度上升很多(主要是因為利用了amortized的方式來分析)。
以下附上一些link你可以去參考一下。
http://www.cse.yorku.ca/~aaw/Jason/FibonacciHeapAnimation.html
http://en.wikipedia.org/wiki/Fibonacci_heap
歡迎一起討論^^..
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.29.250