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