algorithm - Find operation in Fibonacci Heap

Question

I have this question when teaching myself Fibonacci Heap, which now I know is an efficient data structure to implement priority queue with amortized O(1) time complexity when decreasing priority of an element in the heap. However, from the CLRS textbook, the priority decreasing operation assumes the node holding target element is pre-known. I'm curious about how could I get the desired node efficiently if not the minimum node. A naive implementation and analysis yields O(n) worst-case time complexity to perform the find operation on a Fibonacci Heap, which is less efficient compared to other operations. So my question is that is there an efficient find operation in Fibonacci Heap, or is it necessary?

Answer 1

所以第一件事：这个结构被设计成一个高效的优先级队列，而不是搜索结构，所以 find 操作是O(n)。通常您知道要更改的确切节点。让我们看一个例子——Dijkstra 算法。

在每一步中，您将图顶点推送到堆或更改其优先级，因此在顶点中保存指向堆节点的指针是很自然的。这种方式效果很好！

所以基本上你会将指向某个节点的指针存储在某个地方（你可以将它们存储在哈希图或 AVL 树中）。

Answer 2

通过HashMap可以解决问题。Integer 将保存 Fibonacci heap 的键值，相应的 Node 将是它的值。所以删除前不需要搜索节点。斐波那契堆比高度平衡的二叉搜索树更有效，因为斐波那契堆需要 O(1) 的插入时间和 O(logN) 的删除时间。我希望 Fibonacci 将替换 linux 内核中的 Redblack 树，甚至替换 Databases 中的 AVL 树。