在斐波那契堆中查找操作

Question

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

Answer 1

所以第一件事：這個結構被設計成一個有效的優先級隊列，而不是搜索結構，所以查找操作是O(n)。通常你知道你想改變的確切節點。我們來看一個例子 - Dijkstra的算法。

在每一步中，您都會將圖頂點推入堆中或更改其優先級，因此將指針指向頂點中的堆節點是很自然的。這樣它的效果很好！所以基本上你會將指針存儲在某個節點（你可以將它們存儲在散列表或AVL樹中）。