Java Reference
In-Depth Information
73
Original Numbers
6
57
73
6
57
88
60
42
83
72
48
85
88
60
42
83
72
48
85
88
Build Heap
88
85
83
72
73
42
57
6
48
60
85
83
72
73
42
57
6
48
60
85
Remove 88
73
83
85
73
83
72
60
42
57
6
48
88
72
60
42
57
6
48
83
Remove 85
73
57
83
73
57
72
60
42
48
6
85
88
72
60
42
48
6
73
Remove 83
72
57
73
72
57
6
60
42
48
83
85
88
6
60
42
48
Figure7.15
An illustration of Heapsort. The top row shows the values in their
original order. The second row shows the values after building the heap. The
third row shows the result of the first
removefirst
operation on key value 88.
Note that 88 is now at the end of the array. The fourth row shows the result of the
second
removefirst
operation on key value 85. The fifth row shows the result
of the third
removefirst
operation on key value 83. At this point, the last
three positions of the array hold the three greatest values in sorted order. Heapsort
continues in this manner until the entire array is sorted.
