Description
Chapter 6
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:
- show how it could be stored in an array
- give the formulas to find the left, middle, and right children from any parent
- give the formula to find the parent from any child
