Java Reference
In-Depth Information
FIGURE 26-4
An array representation of the steps in Figure 26-3
(a)
90
1
80
60
3
70
30
20
50
10
40
85
30
0
2
4
5
(10/2)
6
7
8
9
10
11
12
(b)
20
90
80
60
70
4
50
7
10
40
30
Move 30
0
12
1
2
3
5
6
8
9
10
11
(c)
90
1
80
2
(5/2)
60
70
20
50
10
40
30
85
80
0
3
4
5
6
7
8
9
10
11
12
(d)
90
60
3
70
80
5
20
50
30
10
40
Move 80
0
1
2
6
7
8
9
10
11
12
4
(e)
90
60
80
20
50
70
10
40
30
85
90
1
(2/2)
5
6
7
8
9
10
11
12
2
3
4
0
(f)
90
85
60
70
80
20
50
10
40
30
Insert 85
0
1
2
3
4
5
6
7
8
9
10
11
12
Question 3
Repeat Question 2 using the previous algorithm without swaps. Show the heap at
each step as a tree and as an array.
26.8
The method
add
.
We now implement the previous algorithm. The
add
method begins by incre-
menting the index
lastIndex
of the last array entry and then checks that the array is large enough
to hold a new entry. If it is not, we double the size of the array, as we have done in previous chap-
ters. (See Segment 2.34 of Chapter 2, for example.) The rest of the implementation closely follows
the pseudocode.
public void
add(T newEntry)
{
lastIndex++;
ensureCapacity();
