[Solved] DataStructure Assignment #6

Chapter 6

100 points total

Questions are 10 points each.

• Show the result of inserting the following values one at a time into an initially empty binary heap. (Show the heap after each insert). Use trees to illustrate each heap.

42, 11, 28, 8, 13, 61, 18

• Show how the final heap created in the previous problem would be stored in an array.
• Show the result after a deleteMin on this binary heap. (Show each step).

3

/

6 10

/ /

15 8 19 21

/ /

20 25 9 11

• Show the result after a deleteMin on this binary heap. (Show each step).

12

/

16 18

/ /

32 25 21 24

/ / / /

40 45 58 50 42 54 48 52

/ /

49 46 59 57

• Show a recursive merge of the following leftist heaps. (Show each step).

h1 h2 4 8

/ /

10 50 12 19

/ / /

13 20 30 14 40

/ /

16 25

• Show a recursive merge of the following leftist heaps. (Show each step).

h1 h2 5 7

/ /

10 19 12 40

/ / / /

13 20 54 30 14 50

/ / /

16 18 25 61 65

• Show a recursive merge of the following skew heaps. (Show each step).

h1 h2

19 11

/ /

54 39 12 30

/ / / /

61 65 68 30 14 50 59

• Show a merge of the following binomial queues. (Show each step).

h1: 8 12 17 |

14 20 21

28

h2: 6 15 9 |

19 11 16

23

• Show a merge of the following binomial queues. (Show each step).

h1: 13 17 22___ | |

20 21 40 45 26

|

28 50 30 32

39

h2: 6 15 9 |

19 11 16

23

• For the 3-heap shown in slide 37:
  1. (2 pts) show how it could be stored in an array
  2. (6 pts) give the formulas to find the left, middle, and right children from any parent
  3. (2 pts) give the formula to find the parent from any child

Submit to eLearning:

hw6.doc (.doc can be .txt, .jpg, etc.)