Typically, when implementing a Fibonacci heap, your implementation of enqueue would return a pointer to the newly-inserted node. That way, you can store the pointer for later use. You're absolutely right that you'd have to spend O(n) time searching for the node if you don't have a pointer to it.
As an example, here's my own personal implementation of a Fibonacci heap. The enqueue
method is given here:
public Entry<T> enqueue(T value, double priority) {
// ...
}
Notice how it returns an Entry<T>
representing that node. The corresponding implementation of decreaseKey
has this interface:
public void decreaseKey(Entry<T> entry, double newPriority) {
// ...
}
Here, the parameter is the Entry<T>
corresponding to the node holding the element whose key should be decreased. It's impossible to call this method without having the Entry<T>
that was returned by enqueue
because otherwise it would be impossible to implement efficiently.
Hope this helps!