Java Reference
In-Depth Information
Continuing at node 3, 43 must be moved. The larger child is 84, so we interchange the values at nodes 3 and 6.
The value now at node 6 (43) is bigger than its child (32), so there is nothing more to do. Note, however, that if the
value at node 6 were 28, say, it would have had to be exchanged with 32.
Moving to node 2, 25 is exchanged with its larger child, 79. But 25 now in node 4 is smaller than 65, its right child
in node 9. Thus, these two values must be exchanged.
Finally, at node 1, 37 is exchanged with its larger child, 84. It is further exchanged with its (new) larger child, 73,
giving the tree, which is now a heap, shown in Figure
9-3
.
1
84
2
3
73
79
4
6
5
7
65
37
69
43
12
11
9
8
10
32
18
25
56
48
Figure 9-3.
The final tree, which is now a heap
9.1.2 The Sorting Process
After conversion to a heap, note that the largest value, 84, is at the root of the tree. Now that the values in the array
form a heap, we can sort them in ascending order as follows:
•
Store the last item, 32, in a temporary location. Next, move 84 to the last position (node 12),
freeing node 1. Then, imagine 32 is in node 1 and move it so that items 1 to 11 become a heap.
This will be done as follows:
•
32 is exchanged with its bigger child, 79, which now moves into node 1. Then, 32 is further
exchanged with its (new) bigger child, 69, which moves into node 2.
Finally, 32 is exchanged with 56, giving us Figure
9-4
.
1
79
2
3
73
69
4
6
5
7
65
37
56
43
11
12
8
9
10
84
18
25
32
48
Figure 9-4.
After 84 has been placed and the heap is reorganized
Search WWH ::
Custom Search