Java Reference
In-Depth Information
5.23 What are the minimum and maximum number of elements in a heap of
height h?
5.24 Where in a max-heap might the smallest element reside?
5.25 Show the max-heap that results from running
buildHeap
on the following
values stored in an array:
10
5
12
3
2
1
8
7
9
4
5.26 (a) Show the heap that results from deleting the maximum value from the
max-heap of Figure 5.20b.
(b) Show the heap that results from deleting the element with value 5 from
the max-heap of Figure 5.20b.
5.27 Revise the heap definition of Figure 5.19 to implement a min-heap. The
member function
removemax
should be replaced by a new function called
removemin
.
5.28 Build the Huffman coding tree and determine the codes for the following set
of letters and weights:
Letter
A
B
C
D
E
F
G
H
I
J
K
L
Frequency
2
3
5
7
11
13
17
19
23
31
37
41
What is the expected length in bits of a message containing n characters for
this frequency distribution?
5.29 What will the Huffman coding tree look like for a set of sixteen characters all
with equal weight? What is the average code length for a letter in this case?
How does this differ from the smallest possible fixed length code for sixteen
characters?
5.30 A set of characters with varying weights is assigned Huffman codes. If one
of the characters is assigned code 001, then,
(a) Describe all codes that cannot have been assigned.
(b) Describe all codes that must have been assigned.
5.31 Assume that a sample alphabet has the following weights:
Letter
Q
Z
F
M
T
S
O
E
Frequency
2
3
10
10
10
15
20
30
(a) For this alphabet, what is the worst-case number of bits required by the
Huffman code for a string of n letters? What string(s) have the worst-
case performance?
(b) For this alphabet, what is the best-case number of bits required by the
Huffman code for a string of n letters? What string(s) have the best-
case performance?
