Bounding Rank of Fibonacci Heap

Bounding Rank of Fibonacci Heap to lgn:
Before understanding the concept see below notations,

1. tree(H)=number of nodes in the root list in below Fibonacci Heap Example
2. rank(x)=number of children it has
3. rank(H)=max rank(x) 

Note: Black nodes are marked nodes (when one of its children is deleted it is marked if it is not already marked).

We have following operation in Fibonacci Heap:

1. Insert - O(1)
2. Union - O(1)
3. Decrease Key - O(1)
4. Delete-Min - O(Rank(H)) = O(lgn)
5. Delete - O(Rank(H)) = O(lgn)

In this blog we will see how the rank is bounded to be lgn.

So some assumptions I have made that you know at a time we cannot delete >1 child of any node.

And after deleting child of a node we make it as Marked Node  if it is not marked already.

Some Background;

Merge Operation: We do merge operation when we do delete minimum. Merge operation is when rank of two nodes is same, we merge them as making minimum of them as root node and other as child of it.

Now when do we merge: When rank of two nodes is same we perform the merge operation

Let's say there is node xi and it has children y1, y2, y3, .....yn, and we are interested in finding the rank of yi

So we say that rank of Rank(yi) >={1.    0 ,   otherwise

                                                           2.    i-2,       i>=2  }

Why do we even say the above statement, read following assertions first:

1. Node xi can >=i - 1 children as one child can be cut.
2. Node yi  would have been merged with xi only when its rank = i-1
3. So we can say the below statement:
4. rank(xi)=rank(yi)>=i-1
5. Now as yi became child of xi, we can remove one more child of yi at max
6. Then rank(yi)>=i-1-1 >= i-2
7. Or in other words: rank(xi)=rank(yi)>=i-2

When we see below diagram:

If you see that in the above diagram for i>=2 for every node the property is satisfying, that if you take any child of Fi it has rank >=i-2, 

As an instance lets take third child of F3, its(third child) rank is 1. (Recall rank is #children)

And quickly just check for every child of Fi whether the property holds true or not.

Note: For i<2 the rank is 0. So only check for i>=2

If you look closely then you will find that last child of Fi  is copy of (Fi-2th in the series).

And the if we ignore the last child of Fi then we could see that Fi-1th tree(in the series).

So this leads us to the below formula:

Minimum number of nodes in F(k) = Minimum number of nodes in F(k-1) + Minimum number of nodes in F(k-2)

Or Simply:

                   F(k) = F(k-1) + F(k-2)

Which is a Fibonacci Sequence formula hence its name Fibonacci Heap.

You also have seen that number of nodes are in Fibonacci sequence in above image.

Now let's proceed further to prove how rank is bounded by lgn:

Let's say we have a Fibonacci Heap H, rank(H) is r, total number of nodes are = n,

By Definition:

F(r) is minimum number of nodes which should be there in Fibonacci Heap whose rank is r.

So,                             n> = F(r)

And we know that, F(r)  = F(r-1) + F(r-2)

                         So,    n >= F(r-1) + F(r-2)

                                  n >= 2*F(r-2)                                                      1.1

Now lets solve 2*F(r-2), and F(0) is 1.

Solve this using back substitution:

=2*F(r-2)

=2^2*F(r - 2*2)

=2^3*F(r - 3*2)

=2^4*F(r - 4*2)

.....

=2^k*F(r - k*2)                                                                                    1.2

So put, 

=> r - k*2 = 0       , as F(0) = 1

=> k = r/2

Now our expression 1.2 will become

=> 2^(r/2)*1 = 2^(r/2)

Put this in expression 1.1

=> n >= 2^(r/2)   or  

=> 2^(r/2) <= n                                                                                   1.3

Take lg to both sides in expression 1.3, we will get below expression:

=> r = 2*lgn

So rank r is O(lgn)

Thanks for Reading

Have a good one!