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?

score 8 · Accepted Answer · answered Jun 05 '13 at 15:21

8

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

answered Jun 05 '13 at 15:21

Piotr Jaszkowski

1,150
9
12

That means I need an extra data structure to maintain all the nodes. (in the Dijkstra's algorithm example it is a graph)? – Summer_More_More_Tea Jun 05 '13 at 15:25
Yes, you want to have the pointers to the nodes stored somewhere so you will have easy access to them. Yes in Dijkstra's algo it's graph. – Piotr Jaszkowski Jun 05 '13 at 15:36
Do you have any reference to some (pseudo) code that implements Dijkstra's that uses a Fibonacci heap? I have searched, but I haven't had any luck in finding such code... – HelloGoodbye Dec 08 '19 at 00:17

score 1 · Answer 2 · answered Aug 07 '19 at 13:15

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 .

Find operation in Fibonacci Heap

2 Answers2