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.

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.