Ppt On Binomial Trees

SHRADDHA GUPTA 3RD CSE 113/05

COMPARISON OF EFFICIENCY Heaps Operation

Linked List

Binary

Binomial

Fibonacci *

Relaxed

make-heap

1

1

1

1

1

insert

1

log N

log N

1

1

find-min

N

1

log N

1

1

delete-min

N

log N

log N

log N

log N

union

1

N

log N

1

1

decrease-key

1

log N

log N

1

1

delete

N

log N

log N

log N

log N

is-empty

1

1

1

1

1

Binomial Tree  Recursive

definition:

The Binomial Tree Bk is an ordered tree defined recursively. Bk consists of 2 Bk-1 trees

Bk

B0

Bk-1 Bk-1

linked together,root of 1 is child of the other

B0

B1

B2

B3

B4

Useful   

properties of order k binomial tree Bk.

Number of nodes = 2k. Height = k. Nodes at depth i=

k    i

Degree of root = k.  Root has degree k which is greater than degree of any other node.

B k+1



Proof. 

By induction on k.

Bk

B2

B1

B0

PROOF BY INDUCTION Let’s assume lemma holds for Bk-1 • Bk has 2k nodes: Bk-1 has 2k-1 nodes Bk ---> 2 copies of Bk-1 binomial trees == 2k-1 + 2k-1 nodes == 2k nodes Proved

2. Height(Bk) =k Let us assume height(Bk-1)=k-1

Bk Bk-1 Bk-1

Root of 1 tree becomes the left child of the other tree So, maximum depth of Bk is 1 greater than that of Bk height(Bk) =(k-1 ) +1 =k

3. A property useful for naming the data structure. 

Bk has  k  nodes at depth i.   i 4  =6 2

At depth 2

depth 0 depth 1 depth 2 depth 3 depth 4

B4

3. Bk has

k    i

nodes at depth i.

Let D(k,i) be the number of nodes at depth i of Bk. Since Bk is composed of 2 Bk-1, a node at depth i in Bk-1 appears in Bk once at depth i and once at i+1. Nodes at depth i in Bk= nodes at depth i in Bk-1 + nodes at depth i-1 in Bk-1 D(k,i) =D(k-1,i) + D(k-1,i-1) =k-1Ci + k-1Ci-1 =

k    i

Binomial Heap Sequence of binomial trees that satisfy binomial heap property. each tree is min-heap ordered 0 or 1 binomial tree of order k (at most 1 binomial tree in H has root of degree k. 

8

45 55

30

23

32

24

22

48

29

10

31

17

6

3

44

37

18

50

B4

B1

B0

H

BINOMIAL HEAP OF GIVEN NUMBER OF NODES Find binary representation of number Ex : 13= 1101 Number of bits used =floor(lg(13))+1 =4 Set of binomial trees present in binomial heap =B0, B2, B3 as bit 1 is present at the positions 0,2,3 

Representing Binomial Heaps Node x; Parent(x) Key(x) Degree(x) Child(x) Sibling(x)

Pointer to parent key degree pointer to pointer to child sibling

H

A binomial heap

15

H

28

7

11

15 0

28 2

7 1

11 0

5 5 0

OPERATIONS ON BINOMIAL HEAP       

Creation of a new Heap Search for minimum key Union of 2 Binomial trees Insertion of a node Extract minimum Decrease key of a node Delete a node

Creating a new Binomial Heap 

Head [H]= NIL Simply allocates and returns an object, H is the newly created Binomial Heap. Running time =

(1)

Finding the minimum key x=head[H], min=infinity, y=NIL While x!=NIL do if key(x)<min then min=key(x) y=x x=sibling(x) Return y 3 H 18

6

8

29

10

31

17

37 30

23

32

24

22

48

O(lg n) running time 45 55

50

44

UNITING 2 BINOMIAL HEAPS Linking 2 Bk-1 trees rooted at y and z y

y>z

z

Linking Bk-1

Bk-1

z y

Bk-1

Bk-1 5

16

5

Linking 25

16

37 25

O(1) running time

37

Binomial-Link(y,z) 1 parent[y]=z 2 sibling[y]=child[z] 3 child[z]=y 4 degree[z]++

n e r pa

y

C

t

) z ( d hil

Sibling

w Procedure takes O(1) time.

z Child(z) x

UNITING HI AND H2 HEAPS 



STEP 1 Make Binomial Heap (empty binomial heap with head= NULL) STEP 2 MERGE the binomial heaps (merging occurs as in merge sort , the root with the lower degree is appended to root of output root list)

H2

6

3

18

37

HEAP 1

45

8

30

23

32

24

22

50

H1 55 12

7

25

15

28 41

33

48

HEAP2

29

10

31

17

44

3

18

H2

6

H1 12

7

37

15

25

28

33 45

41

8

30

23

32

24

22

48

29

10

31

17

50 6

55

H H 12 12

18

7 18 25

15

3 7 37 25

44

8

15 29

10

30

23 28 22

48 33 31

17

32

24 41

50

3 28

33 37

41 45

44

After Merging  STEP 3 IF HEAD(H) = null RETURN H  STEP 4 x=HEAD(H) CASE1: degree(x)<degree(next-x) MOVE AHEAD CASE2: degree(x)=degree(next-x) =degree(sibling(next-x)) MOVE AHEAD

CASE 3: Degree(x)=degree(next-x) != degree(sibling(next(x)) If( key(x)< key(next(x)) BINOMIAL-LINK(next-x,x) Else BINOMIAL-LINK(x,next-x)

H x 12

6

Next-x 18

7 25

15

3 37

28 41

45

CASE 3

8

33 30

23

32

24

55

Degree(x)=degree(next-x) != degree(sibling(next(x)) If( key(x)< key(next(x)) BINOMIAL-LINK(next-x,x)

22

48

50

29

10

31

17

44

H

x 12

18

6

Next-x 7 25

15

3 37

28

8

33

41

45

30

23

32

24

55

CASE2: degree(x)=degree(next-x) =degree(sibling(next-x)) MOVE AHEAD

22

48

50

29

10

31

17

44

H

Prex x 12

18

x 7 25 7

Next x

x x Next

15

3 37

28

8

33

41 25 45 55 CASE 3: Degree(x)=degree(next-x) != degree(sibling(next(x))

BINOMIAL-LINK(x,next-x)

6

30

23

32

24

22

48

50

29

10

31

17

44

Next x H

Prev x

x

6

3

12

18

15 28 41

33

7

8

37

25 45

30

23

32

24

55

UNION OF 2 BINOMIAL HEAPS

22

48

50

29

10

31

17

44

INSERT INTO BINOMIAL HEAP(H1) 1 Make a new Binomial Heap H1 2 H <- BINOMIAL HEAP UNION (H, H1) H H1

Null

O(lg n) running time

EXTRACT MINIMUM NODE 1 Search minimum node ‘x’ and remove it from root list 2 H1 <- make binomial heap 3 reverse the order of the linked list of x’s children and set head(H1) to point to the head of resulting list 4 H <- BINOMIAL HEAP UNION(H,H1) Return x