Java Reference
In-Depth Information
Program P9.2 will build the heap (described next) and print the following:
84 79 73 48 69 37 65 18 25 43 56 32
After
37
,
25
, and
43
are read, we will have Figure
9-9
.
1
1
1
37
37
43
3
2
2
25
25
37
Figure 9-9.
Heap after processing 37, 25, 43
After
65
,
48
,
84
, and
73
are read, we will have Figure
9-10
.
1
84
2
3
73
48
4
6
5
7
25
65
43
37
Figure 9-10.
Heap after processing 65, 48, 84, 73
And after
18
,
79
,
56
,
69
, and
32
are read, we will have the final heap shown in Figure
9-11
.
1
84
2
3
73
79
4
6
5
7
48
65
69
37
11
12
8
9
10
32
18
25
43
56
Figure 9-11.
Final heap after processing 18, 79, 56, 69, 32
Note that the heap in Figure
9-11
is different from that of Figure
9-3
even though they are formed from the same
numbers. What hasn't changed is that the largest value,
84
, is at the root.
If the values are already stored in an array
num[1..n]
, we can create a heap with the following:
for (int k = 2; k <= n; k++) siftUp(num, k);
Search WWH ::
Custom Search