Blog

DESIGN AND ANALYSIS OF ALGORITHMS ASSIGNMENT-1 TOPIC

DESIGN AND ANALYSIS OF ALGORITHMS
ASSIGNMENT-1
TOPIC: FIBONACCI HEAPS
SUBMITTED BY: SHUBHAM UPADHYAY (16BCS053)
INTRODUCTION:
Michael L. Fredman and Robert E. Tarjan developed Fibonacci heaps in the year 1984.

Fibonacci heaps are the implementation of heaps that makes use of Fibonacci numbers (1, 1, 2, 3, 5, 8, 13, 21).
Fibonacci heaps are a data structure that is used for an asymptotically faster implementation of Prim’s Minimum Spanning Tree algorithm and Dijkstra’s Shortest Paths algorithm. Fibonacci heaps help in improving the running time of these algorithms.

We Will Write a Custom Essay Specifically
For You For Only $13.90/page!


order now

Fibonacci numbers are the terms of a sequence where every term is the sum of its previous two terms, where:
First term: T(1) = 1
Second term: T(2) = 1
And nth term: T(n) = T(n-1) + T(n-2) for all n > 2
Therefore, generating the sequence: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89…………………………
Fibonacci heaps have a faster amortized* running time as compared to other types of heaps. Fibonacci heaps are similar to binomial heaps but having one very significant difference, that, Fibonacci heaps have a less rigid structure. Binomial heaps merge heaps immediately on the other hand Fibonacci heaps wait to merge until the extract-min function is called/executed. Fibonacci heaps have very good theoretical complexities but in practice, other heap types such as pairing heaps are faster. This is because Fibonacci heaps always require four pointers for each node while other heaps need two or three. In Fibonacci Heaps, trees can take any form, even all trees can be single nodes (This is unlike the Binomial Heap where every tree has to be a Binomial Tree).

Amortized analysis is the method of analyzing the costs associated with a data structure that averages the worst operations out over time. Often, a data structure has one particular operation which is costly, but it doesn’t get performed very often. That data structure should not be labelled a costly structure just because of that one operation.

The table below shows the amortized running time of the various operations performed during the construction/evaluation of Fibonacci heaps.

Operation performed Amortized running time
Insert O(1)
Remove O(log n)
Find min O(1)
Extract min O(log n)
Decrease key O(1)
Merge O(1)
Unlike Fibonacci heaps, Binomial heaps require a running time of O(log n) for each of the associated operations.

We can clearly see from the table that except the remove and extract operation every other operation requires only O(1) amortized running time hence, making Fibonacci heaps more optimized data structures than any other type of heap.

STRUCTURE OF FIBONACCI HEAPS:
Fibonacci heap is a collection of heap-ordered trees. The trees in a Fibonacci heap need not be binomial trees.

Below is an example of a Fibonacci heap (H):
min H
308800563500
548640017589526
0026
413385017970519
0019
15621001943109
009
30670519685025
0025
28689301778005
005

46405801638303316605154305
32404061403350024301451422400020116806985008115306985
30689552540005878830-12705488305215910439293021590
344995514097038
0038
210693012192021
0021
281178012192054
0054
593598012192048
0048
519303012192028
0028
413575515049532
0032

2335530179705003707130189231005488305170180
344805017653043
0043
210693017526041
0041

52197002921037
0037

Fig. 1
The above figure represents a Fibonacci heap consisting of five heap-ordered trees and 14 nodes.
The red lines indicate the root list.

The minimum node of the heap is the node with key 5.

The three marked nodes are represented by highlighting with black color.

The trees within binomial heaps are ordered but the trees within Fibonacci heaps are rooted and unordered. Each node n contains a pointer Pn to its parent and a pointer CHILDn to any one of its children. The children of n are linked together in a circular, doubly linked list, which we call the child list of n. Each child x in a child list has pointers LEFTx and RIGHTx that point to x’s left and right siblings, respectively. If node x is an only child, then leftx = rightx = y. The siblings in a child list are ordered in an arbitrary fashion.

A given Fibonacci heap H is accessed by the pointer min H which points to the root of the tree containing the minimum key; in the above diagram, the min H pointer points to the node with the value 5 as it the minimum value root in the structure.

POTENTIAL FUNCTION:
The potential function is used to analyze the performance of Fibonacci heap operations. For a given Fibonacci heap H, let us say that t (H) be the number of trees in the root list of H and let m (H) be the number of marked nodes in H. The potential of Fibonacci heap H is defined by:
?(H) = t(H) + 2m(H) Eq. 1
From the above equation we can find the potential of the structure in figure 1:
t(H) = 5
m(H) = 3 (the darkened nodes)
Therefore, ?(H) = 5 + 2*3 = 11
Note: Potential of a set of Fibonacci heaps is the sum of the potentials of its constituent Fibonacci heaps.

MERGEABLE-HEAP OPERATIONS:
The Fibonacci heap is designed to contain the nodes which we are currently considering for addition to the growing root component. Hence, the following operations are required:
Let us assume a heap (H).

1. insert (v, H): Insert element v into the structure H (together with an associated value).

2. delete-min (H): Find the element with the smallest associated value in H, return it, and remove it from H.

3. decrease (v, d): Decrease the value associated with node v by d. This required if we discover a new (and cheaper) way of adding the node v. At that point of time, the element v is not yet in the component including the root, but it may just have become a more attractive candidate for inclusion in the next step.

Inserting a node:
INSERT(v, H)
811530101600 degree v 0
48577594615 pv NIL
61912575565 childv NIL
495300123825 leftv v
619125123825 rightv v
65722585725 markv FALSE
concatenate the root list containing v with root list H
if minH = NIL or keyv < keyminH
110490085725 then minH v
40957595250 nH nH + 1
Example:
20578146858023
0023
Consider the figure 1:
Now we need to insert the node in the existing heap: following the above algorithm we can successfully
insert this node into fig. 1 which will be updated as: The new node/element becomes its own heap-ordered tree and is then added to the root list, becoming the left sibling of the root (min H).

min H
308800563500
168592518542023
0023
9048751847859
009
11620518732525
0025
548640017589526
0026
413385017970519
0019
28689301778005
005

46405801638303316605154305
136398076200215455576200062103176200324040614033500243014514224000
30689552540005878830-12705488305215910439293021590
344995514097038
0038
210693012192021
0021
281178012192054
0054
593598012192048
0048
519303012192028
0028
413575515049532
0032

2335530179705003707130189231005488305170180
344805017653043
0043
210693017526041
0041

52197002921037
0037

Fig. 2
Extracting the Minimum Node:
FIB-HEAP-EXTRACT-MIN makes a root out of each child of the minimum node and removes the minimum node from the root list.

Next, it consolidates the root lost by linking roots if equal degree until at most one root remains of each degree.
Consolidate(H) consolidates the root list of H until every root in the root list has a distinct degree value by executing repeatedly the following steps:
1. Find the 2 roots x and y in the root list having same degree, where keyx ? keyy.

2. Link node y to node x: remove y node from the root list, and make y a child of x. The degreex is incremented, and any mark on y is cleared.

The procedure CONSOLIDATE uses an auxiliary array A 0: : D(nH); if Ai = y, then y is currently a root with degreey = i.

Following is the pseudo-code/ algorithm to perform the above two operations:
FIB-HEAP-EXTRACT-MIN(H)
z minH
if z ? NIL
then for each child x of z
do add x to the root list of H
px NIL
remove z from the root list of H
if z = rightz
then minH NIL
else minH rightz
CONSOLIDATE(H)
nH nH – 1
return z
CONSOLIDATE(H)
for i 0 to D(nH)
do Ai NIL
for each node/element w in the root list of H
do x w
d degreex
while Ad ? NIL
do y Ad
if keyx > keyy
then exchange x y
FIB-HEAP-LINK(H, y, x)
Ad NIL
d d + 1
Ad x
minH NIL
for i 0 to D(nH)
do if Ai ? NIL
then add Ai to the root list of H
if minH = NIL or keyAi < keyminH
then minH Ai
FIB-HEAP-LINK(H, y, x)
remove y from the root list of H
make y a child of x, incrementing degreex
marky FALSE
Now let us consider an example to understand these 2 operations:
Consider the following fibonacco heap:
min H
308800563500
168592518542023
0023
9048751847859
009
11620518732525
0025
548640017589526
0026
413385017970519
0019
28689301778005
005

46405801638303316605154305
136398076200215455576200062103176200324040614033500243014514224000
30689552540005878830-12705488305215910439293021590
344995514097038
0038
210693012192021
0021
281178012192054
0054
593598012192048
0048
519303012192028
0028
413575515049532
0032

2335530179705003707130189231005488305170180
344805017653043
0043
210693017526041
0041

52197002921037
0037

Step 1: Extract the minimum and perform the consolidate operation
135933219748523
0023
7668771974859
009
6837719685025
0025
272867616319554
0054
200965317986721
0021
345441615377438
0038
548640017589526
0026
413385017970519
0019

1204525205105002488710135890003242798158750003952850137256004640580163830
1830419889000567893889000225669519420300370611719420200
5878830-12705488305215910439293021590
20091401403841
0041
345757511493543
0043
593598012192048
0048
519303012192028
0028
413575515049532
0032

5488305170180
52197002921037
0037

Step 2:
0 1 2 3
44788171193 93831161466 213887155521

548005019578326
0026
412432516233019
0019
345059018960838
0038
272732511005854
0054
200045315367021
0021
134683518585223
0023
7670801792739
009
5735318034025
0025
x
1204525205105002488710135890003242798158750003952850137256004640580163830
1830419889000567893889000225669519420300370611719420200
5878830-12705488305215910439293021590
20091401403841
0041
345757511493543
0043
593598012192048
0048
519303012192028
0028
413575515049532
0032

54381401562100
51953673556037
0037

Merge 9, 25
As 9 and 25 have the same degree therefore we have to merge them into tree where 25 will become the child of 9
0 1 2 3
44788171193 93831161466
548005019578326
0026
412432516233019
0019
345059018960838
0038
272732511005854
0054
200045315367021
0021
134683518585223
0023
7670801792739
009
x
1204525205105002488710135890003242798158750003952850137256004640580163830
2259330204673001830419889000370611719420200
97536010160005878830-12705488305215910439293021590
729385508025
0025
20091401403841
0041
345757511493543
0043
593598012192048
0048
519303012192028
0028
413575515049532
0032

54381401562100
51953673556037
0037

Merge 9, 19
As 9 and 19 have the same degree therefore we have to merge them into tree where 19 will become the child of 9
0 1 2 3
93831161466
548005019578326
0026
345059018960838
0038
272732511005854
0054
200045315367021
0021
134683518585223
0023
7670801792739
009
x
395802316519500120452520510500248871013589000324279815875000
359599155278002259330204673001830419889000370611719420200
11366519664719
0019
97536010160005878830-12705488305215910
729385508025
0025
20091401403841
0041
345757511493543
0043
593598012192048
0048
519303012192028
0028

358978254000054381401562100
1259332222532
0032

51953673556037
0037

Merge 9, 26
As 9 and 26 have the same degree therefore we have to merge them into tree where 26 will become the child of 9
0 1 2 3
132337153616 174981342464104070132736

136608818542023
0023
345059018960838
0038
272732511005854
0054
200045315367021
0021
7670801792739
009
x
120452520510500248871013589000324279815875000
108937615912800359599155278002259330204673001830419889000370611719420200
11366519664719
0019
9753601016000
13121402857526
0026
729385508025
0025
20091401403841
0041
345757511493543
0043

131311216892400
16438531309200164190720510548
0048
3589782540000
10934971079528
0028
1259332222532
0032

13246109418300107759527114537
0037

Merge 23, 54
0 1 2 3
22566954126198237221806

316432718542023
0023
430296315367021
0021
550753118923038
0038
7670801792739
009
x
120610817757000474915117716500
364002988900045311572044700057729881936750010893761591280035959915527800
3409950268730011366519664719
0019
9753601016000
31667455036854
0054
42933571397041
0041
552175711493543
0043
13121402857526
0026
729385508025
0025

131311216892400
16438531309200164190720510548
0048
3589782540000
10934971079528
0028
1259332222532
0032

13246109418300107759527114537
0037

Merge 21, 23
0 1 2 3
22566954126198237221806

430296315367021
0021
550753118923038
0038
7670801792739
009
x
120037114541500474915117716500
35062771514610045311572044700057729881936750010893761591280035959915527800
316420518075423
0023
11366519664719
0019
9753601016000
42933571397041
0041
552175711493543
0043
13121402857526
0026
729385508025
0025

131311216892400
3409950351460016438531309200164190720510548
0048
3589782540000
31667455502454
0054
10934971079528
0028
1259332222532
0032

13246109418300107759527114537
0037

STOP
ANALYSIS:
The potential before extraction of minimum node is t(H) + 2m(H), and the potential after extraction is at most (D(n) + 1) + 2m(H), since at most D(n) + 1 roots remain at the end and no nodes become marked during the operation. The amortized cost is thus: (maximum)
O(D(n) + t(H)) + ((D(n) + 1) + 2m(H)) – (t(H) + 2m(H))
= O(D(n)) + O(t(H)) – t(H)
= O(D(n)).

DECREASING A KEY:
Following is the method/algorithm for decreasing a key in the Fibonacci heap structure:
FIB-HEAP-DECREASE-KEY(H, x, k)
if k > keyx
then error
keyx k
y px
if y ? NIL and keyx < keyy
then CUT(H, x, y)
CASCADING-CUT(H ,y)
if keyx < keyminH
then minH x
CUT(H, x, y)
remove x from the child list of y, and decrement degreey
add x to the root list of H
px NIL
markx FALSE
CASCADING-CUT(H, y)
z py
if z ? NIL
then if marky = FALSE
then marky TRUE
else CUT(H, y, z)
CASCADING-CUT(H, z)
Let us consider one example:
Suppose we have to decrease 48 to 17
430296315367021
0021
550753118923038
0038
7670801792739
009

120037114541500474915117716500
35062771514610045311572044700057729881936750010893761591280035959915527800
316420518075423
0023
11366519664719
0019
9753601016000
42933571397041
0041
552175711493543
0043
13121402857526
0026
729385508025
0025

131311216892400
3409950351460016438531309200164190720510548
0048
3589782540000
31667455502454
0054
10934971079528
0028
1259332222532
0032

18916655927600164614124384037
0037
13246109418300107759527114537
0037

Step 1: Decrease the key of 48 to 17 and cut the link between 48 and its parent.

430296315367021
0021
550753118923038
0038
7670801792739
009

120037114541500474915117716500
35062771514610045311572044700057729881936750010893761591280035959915527800
316420518075423
0023
11366519664719
0019
9753601016000
42933571397041
0041
552175711493543
0043
13121402857526
0026
729385508025
0025

131311216892400
34099503514600164190720510517
0017
3589782540000
31667455502454
0054
10934971079528
0028
1259332222532
0032

18916655927600164614124384037
0037
13246109418300107759527114537
0037

Step 2: Mark the parent and add tree rooted to 48 to the root list updating the heap min pointer if required.

625706919939017
0017
430296315367021
0021
550753118923038
0038
7670801792739
009

599843520637500120037114541500474915117716500
35062771514610045311572044700057729881936750010893761591280035959915527800
65261164318000316420518075423
0023
11366519664719
0019
9753601016000
6279736508037
0037
42933571397041
0041
552175711493543
0043
13121402857526
0026
729385508025
0025

131311216892400
340995035146003589782540000
31667455502454
0054
10934971079528
0028
1259332222532
0032

13246109418300107759527114537
0037

Analysis:
Let us calculate the change in potential. Let H denote the heap just before the FIB-HEAP-DECREASE-KEY operation is executed. For each recursive call of CASCADING-CUT, except for the last one, it will cut a marked node and it will clear the mark bit.
Afterwards:
there are t(H) + c trees and at most m(H) – c + 2 marked.
Therefore, the change in potential is (maximum)((t(H) + c) + 2(m(H) – c + 2)) – (t(H) + 2m(H)) = 4 – c .

Thus, the amortized cost of FIB-HEAP-DECREASE-KEY will be (at most)
O(c) + 4 – c = O(1), because we can scale up the units of potential to dominate the constant hidden in O(c).

DELETING A NODE:
Following is the pseudo code to perform the delete operation in a Fibonacci Heap:
FIB-HEAP-DELETE(H, x)
FIB-HEAP-DECREASE-KEY(H, x, -?)
FIB-HEAP-EXTRACT-MIN(H)
The deletion operation can be performed in an amortized time of O(log n).

UNION OF TWO FIBONACCI HEAPS:
Following is the procedure to perform the union operation on 2 Fibonacci heaps:
FIB-HEAP-UNION(H1, H2)
H MAKE-FIB-HEAP()
minH minH1
concatenate the root list of H2 with the root list of H
if (minH1 = NIL) or (minH2 ? NIL and minH2 < minH1)
then minH minH2
nH nH1 + nH2
free the objects H1 and H2
return H
Let us consider an example:
4499610127414
432286131721 min min
571268186360308800563500
641200918351519
0019
548640017589526
0026
413385017970590
0090
15621001943109
009
30670519685025
0025
28689301778005
005

46372671631402005882163140
598898988358107029000324040614033500243014514224000
30689552540005878830-12705488305215910
344995514097038
0038
210693012192021
0021
281178012192054
0054
593598012192048
0048
519303012192028
0028

2335530179705003707130189231005488305170180
344805017653043
0043
210693017526041
0041

52197002921037
0037

H1 H2
Concatenate the root list of both the heaps into new root list. (Say H) and set the minimum in H.

315840715268869350383079
45995816602
641200918351519
0019
548640017589526
0026
413385017970590
0090
15621001943109
009
30670519685025
0025
28689301778005
005
min
46372671631402005882163140
598898988358107029000324040614033500243014514224000
30689552540005878830-12705488305215910
344995514097038
0038
210693012192021
0021
281178012192054
0054
593598012192048
0048
519303012192028
0028

2335530179705003707130189231005488305170180
344805017653043
0043
210693017526041
0041

52197002921037
0037

BOUNDING THE MAXIMUM DEGREE:
This concept basically governs maximum degree of a tree in Fibonacci Heap. It states that- If all the individual trees in the Fibonacci Heap are unordered binomial trees, then D(n) = log 2 n. But the cuts (cascading cuts) may cause the occurrence of trees that are not unordered binomial trees. Therefore, a slightly weaker result holds:
D(n) ? log  n. Where is defined as the Golden Ratio = 1.61803.

x

Hi!
I'm Gloria!

Would you like to get a custom essay? How about receiving a customized one?

Check it out