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:
- (2 pts) show how it could be stored in an array
- (6 pts) give the formulas to find the left, middle, and right children from any parent
- (2 pts) give the formula to find the parent from any child
Submit to eLearning:
hw6.doc (.doc can be .txt, .jpg, etc.)
Reviews
There are no reviews yet.