Java Reference
In-Depth Information
FIGURE 26-9
A trace of heap sort
Array view
Tree view
20
30
40
20
40
30
10
90
70
(a) The original array
10
90
70
Heap
90
40
70
90
40
70
10
20
(b) After creating
a heap
30
30
10
20
Swap
Tree
Sorted
30
40
70
(c) After swapping
30
40
70
10
20
90
10
20
Heap
70
40
30
(d) After
reheap
70
40
30
10
20
90
10
20
Swap
Tree
Sorted
20
40
30
20
40
30
10
70
90
(e) After swapping
10
Heap
40
20
30
(f) After
reheap
40
20
30
10
70
90
10
Swap
Tr e e
Sorted
10
10
20
30
40
70
90
20
30
(g) After swapping
Heap
30
30
20
10
40
70
(h) After
reheap
90
20
10
Swap
Tree
Sorted
10
(i) After swapping
10
20
30
40
70
90
20
Heap
20
(j) After
reheap
90
20
10
30
40
70
10
Swap
Tree
Sorted
10
10
20
30
40
70
90
(k) After swapping
Sorted
10
20
30
40
70
90
(l) Array is sorted
