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

So first thing: this structure was designed to be an efficient priority queue, not search structure so find operation is O(n). Normally you know exact node you want to change. Let's look on an example - Dijkstra's algorithm.

In every step you push graph vertex to the heap or change its priority so it's natural to hold pointer to the heap node in vertex. This way it works great!

So basically you will store the pointer to a node somewhere (you can store them in a hashmap or AVL tree).

Answer 2

By HashMap the problem can be solved . The Integer will hold the key value of Fibonacci heap and the corresponding Node will be its value . So no need to search for the node before deletion . Fibonacci heaps is more efficient than height balanced binary search trees , since Fibonacci heaps require O(1) time for insertion and O(logN) time for deletion . I hope Fibonacci will replace Redblack trees in linux kernels and even replace AVL trees in Databases .