fibonacci-heap

10熱度

1回答

是否有可用於Haskell的斐波那契堆/優先級隊列？（？甚至是漸近更好的），我發現不同的優先級隊列實現的列表中this question，但我找不到其中的任何符合斐波那契堆的攤銷運行時間：查找最小爲O（1）攤銷時間。操作插入，減少鍵和合並（聯合）工作是O（1）攤銷時間。操作刪除和刪除最小值爲O（log n）攤銷時間。請參閱the comparison of theoretic bound

12熱度

1回答

爲什麼斐波納契堆需要級聯切割？

我正在從'算法介紹'學習f-heap，'減少鍵'操作真的讓我困惑 - 爲什麼這需要'級聯切割'？如果該操作被移除：補充堆（），插入（），最小（）和接頭（）的成本仍然明顯不變提取-MIN（）是仍然是O （D（n）），因爲在O（n（H））'合併'操作中，大多數有根樹的成本可以在支付時支付，當它們被添加到根列表時，剩餘的成本O（D n））遞減鍵（）：顯然O（1）至於D（n），雖然我無法準確解釋

3熱度

1回答

如何通過句柄從boost :: fibonacci_heap獲取元素？

我正在使用Boost 1.53.0中的boost::fibonacci_heap類來維護可更新的優先級隊列。當我想更新一個元素時，我需要將堆中的元素與我想用它替換的新元素進行比較。我只想用「更小」的版本替換堆中的元素，所以我想在更新之前對它們進行比較。當我插入元素時，我存儲它們的句柄（boost::fibonacci_heap::handle_type）。我在documentation for

2熱度

1回答

在斐波那契堆中查找操作

當我自學自己的斐波那契堆時，我有這個問題，現在我知道這是一個高效的數據結構，用於在堆中降低堆中元素的優先級時實現優先級隊列，延遲時間複雜度爲O(1)。但是，從CLRS教科書中，優先級降低操作假定節點保持目標元素是預知的。我很好奇我怎麼纔能有效地獲得所需的節點，如果不是最小節點。一個天真的實現和分析會產生O(n)最差情況下的時間複雜度，以在斐波那契堆上執行查找操作，與其他操作相比效率較低。所

1熱度

1回答

實現鞏固在斐波那契堆

中的僞來自Introduction to Algorithms狀態： for each node w in the root list of H link trees of the same degree 但如何高效地實現每個根節點一部分？在整合過程中，原始根與同一度的其他根相關聯，這使得僅通過根節點的循環列表就很困難。我怎樣才能決定我是否檢查過每個根節點？

1熱度

1回答

如何顯示具有n個節點的斐波納契堆可以有高度n？

我想表明一個有n個節點的斐波那契堆可以有高度n。我試過這個例子，但我不知道如何顯示這一般。

0熱度

1回答

FibonacciHeap increase_key implementation

。嗨，大家好，我使用埃雷爾西格爾的C++ STL斐波那契堆http://ideone.com/9jYnv，我認爲這是缺乏increase_key（）方法。 /** * template Fibonacci Heap * * @ref http://en.wikipedia.org/wiki/Fibonacci_heap * @ref http://www

14熱度

2回答

爲什麼斐波納契堆稱爲斐波那契堆？

Fibonacci heap數據結構名稱中包含「Fibonacci」這個詞，但數據結構中似乎沒有使用斐波納契數字。根據維基百科的文章：斐波那契堆的名稱來自運行時分析中使用的斐波那契數。這些斐波那契數如何在Fibonacci堆中出現？

2熱度

3回答

的Java：使用斐波那契堆在這裏實現Dijkstra算法

新，但都被潛伏作爲嘉賓在相當一段時間:) 好了，所以我一直在嘗試使用斐波納契做Dijkstra的最短路徑算法堆（Java）。經過一番搜索之後，我設法絆倒了代表Fibonacci堆的兩個現成實現。第一個實現相當出色，可以找到here。第二種實現看起來不那麼優雅，是here。現在，這一切看起來不錯，很好。但是，我想爲我的Dijkstra算法的版本使用這些實現之一，但我還沒有任何運氣。 Dijkstr

1熱度

1回答

在已經失去2個或更多子女之後促銷一個節點

在斐波納契堆的decrease-key操作中，如果允許在切割節點並將其融合到根列表（促銷節點）之前丟失s > 1孩子，是否會改變整體運行時複雜度？我認爲複雜性沒有變化，因爲潛在變化將是相同的。但我不確定我是否正確。如何通過攤銷分析證明這一點？