作者justim (透明石油)
看板Prob_Solve
標題[問題] 費氏佇列的問題
時間Sat May 10 14:33:38 2008
最近在讀有關 Fibonacci Heap 的資料 (Horowitz 那本書)，
讀到 cascading cut 那節有點疑惑。照書中的描述是，若一
個 node 之前曾經失去過一個 sub-tree，之後再被移去一個
sub-tree 的話，那就要啟動 cascading cut 的操作。
我的問題是：這樣設計背後的理念是什麼？
書上用了一整段來說明，我濃縮一下：
那是為了保証每個 degree 為 k 的 min-tree 都至少
有 c^k 的 nodes (for some c, c > 1)。
請問我的理解是正確的嗎？
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.116.247.169