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?
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).