Re: [問題] 資料結構的費氏堆積F-Heap
看板CSSE (電腦科學及軟體工程)作者supergothere (人生只有一次)時間15年前 (2009/03/06 13:59)推噓1(1推 0噓 0→)留言1則, 1人參與討論串2/2 (看更多)
※ 引述《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
推
03/06 23:21, , 1F
03/06 23:21, 1F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 2 篇)：
CSSE 近期熱門文章
PTT數位生活區 即時熱門文章
