The Fibonacci Heaps

One fine morning, I heard my mom shouting at me…" What the hell is this? Look at your room. Why don’t you learn to arrange things properly? Blah blah and BLAH...” . I bet, this is the scene in your home too (if you are a lazy kid ) I never felt the importance of organizing things until I realized that searching of certain things becomes really difficult when you don’t arrange your things. Being a computer enthusiast, I wondered how such large amount of data was organized in computer. Later I was enlightened() by the amazing concept of Data Structures that binds everything together in an organized way.

Coming to Data Structures, it is a particular way where in data is organized and stored so that it can be used efficiently. Array, Hash table, stacks, queues, binary heap, Linked Lists are few popular data structures. In this blog, we'll discuss another ingenious data structure known as Fibonacci Heaps.

Fibonacci heap!! Fibonacci series and Heaps !! Whoa..Two amazing concepts spliced together !! Michael L. Fredman and Robert E. Tarjan are the brains behind it.

Let us start the kindergarten of Fibonacci heap

Level 0: Pre- Requisites

In order to understand this, it’s good if you have a prior knowledge about the data structure circularly doubly linked list. If you can’t recall what it is,just take a look at the figure below.

What you need to know is just this:

1. Inserting or removing a node from any location is done in O(1) time.
2. Given two circularly doubly linked lists, we can concatenate them into one list in O(1) time.

Another basic concept of heap should be known.

Min-Heap : A heap in which the value of the parent node is less than that of the child nodes.

We are done with the pre-requisites. Just make sure that you are thorough with it.
Level 1: Structure of a node in Fibonacci heap.

‘A picture speaks a thousand words’. So, it is very important to know “What does it look like?". So, here we are!!

Siblings: Children of same node are called siblings. Obvious isn’t it? :)

Node label: Name of the node.

Key: Information that the node holds.

Degree: It is a attribute of a node to indicate the number of children it has.

Mark : It is a Boolean value which indicates if it has lost one of its child or not

Child: A pointer of a node that points to any one of its children.

Structure of a Fibonacci Heap:

• Fibonacci heap is a collection of many trees.
• Roots of such trees form the root list.
• H.min is a heap attribute that points to the minimum in the root list.

One important thing to be noted is that the values in the root list are unordered but the trees in the heap are min-heap ordered.

Level 3: Operations.

• MAKE-FIB-HEAP :

A home is constructed for Fibonacci heap to live in :P That is, it allocates memory for the heap to be created. This function returns a Fibonacci heap object H, but there are no trees in H.

• INSERT (H, x) : H is the Heap. x is the node label.

There are two possibilities. If it is the first node being inserted, then H.min points to it. Else a new node inserted becomes left sibling of the H.min node by convention.

• Finding the minimum node: Accessing the H.min gives the minimum.

• UNION (H1, H2):

This function plays a role of a broker who bonds two heaps into one with minimum commission

If H1 and H2 are two heaps, then a new heap, H = H1 +H2. H1 and H2 are destroyed.

• Extract-Minimum (H):

The H.min is extracted. Now that the children of H.min are orphans (not a technical term), they are sheltered in the root list But as the root list has to be optimized, CONSOLIDATE function is used to set everything right. It aims at having nodes in the root list with distinct degree in order to minimize the number of elements in the root list.

• · Decrease Key (H, x, k):

Given a node label in a heap, its key can be decreased to desired extent. Later the heap is restructured to preserve its property by CUTS and CASCADING CUTS.

1. Say a node G is marked and has a child P.

2. P has children X and Y.

3. As a result of some operation say P lost its child Y. Now P is marked and is left with the only child 'X'.

4. Lets say the node 'X' is decreased by a finite amount.

5. There are two possibilities.

a. H.min < X.key

b. X.key < H.min (Violation of the heap min-heap property)

6. What we know is that H.min has to be sheltered in root list and H.min is the minimum among all the other elements of heap. Hence we just CUT the node X and is attached as the left sibling of the H.min(again by convention).

7. Now due to Decrease-Key operation even X will have to part from P which means P is losing its second child. Unfair right?

8. Hence P is detached from G and attached as the left sibling of the H.min now. This detachment is termed as CASCADING CUT.

9. But what about G? G is marked and has already lost one of its child. To add to the sorrows, it losing P now. Hence G is detached from its parent and added into the root list as the left sibling of H.min.

10. This goes on till it encounters a node which is unmarked. These are called CASCADING CUTS which are recursive in nature.

If you got stuck somewhere, please take a look at this figure.

(Click on it to get a clear view)

• Delete Key:

What do you think is the obvious way of doing it?

Firstly decrease the key to -∞ and extract the minimum. The node gets deleted.

Why is this better?

‘A stitch in time saves nine’. This proverb stands as a backbone in all walks of life and so in computer science. The true usefulness of the data structure is decided based on the time it takes to perform certain operations on it.

Now let’s compare with the time complexities of two different data structures. Binomial Heaps and Fibonacci heaps. Similar in structure, but with different characteristics.

Here we look at the amortized time it takes to perform all these operations. Clearly, Fibonacci heaps are way better when compared to the time complexity of the binomial heaps.

Why the name ‘Fibonacci’ heap?

We have come almost to the end of the story and still we haven’t justified the name given to it. Formally speaking,.

If F_k represents the k^th Fibonacci number, then the size of a node x is always greater than F_k+2, where k is the degree of the node x.

Size(x) is nothing but the size of the tree rooted at x i.e. the number of nodes it holds including itself.

Let us take the example of this figure.

By the rule,

Which is true

Hence this is a part of Fibonacci heap. Basically, the idea of Fibonacci series is plugged into the concept of heap and all together a new data structure called ‘Fibonacci Heap’ is formed.

If you did not understand any of the above, here is the essence of it. Fibonacci heap is a data structure which is desirable when the number of EXTRACT-MIN and DELETE operations is small relative to the number of other operations performed. It is an efficient data structure. It finds its application in Dijkstra's algorithm, Minimum Spanning Tree etc. For more details on this, please download

http://www.filestube.com/c/cormen+algorithms+pdf

By the way, my Mom is a sweet lady and so am I

Shruthi R Nayak