Java Reference
In-Depth Information
num[root] = key;
} //end siftDown
} //end class HeapSortTest
When run, Program P9.1 produces the following output (
num[1]
to
num[12]
sorted):
18 25 32 37 43 48 56 65 69 73 79 84
Programming
note
: As written,
heapSort
sorts an array assuming that
n
elements are stored from subscripts
1
to
n
. If they are stored from
0
to
n-1
, appropriate adjustments would have to be made. They would be based mainly
on the following observations:
•
The root is stored in
num[0]
.
The left child of node
•
h
is node
2h+1
if
2h+1 < n
.
The right child of node
•
h
is node
2h+2
if
2h+2 < n
.
•
The parent of node
h
is node
(h-1)/2
(integer division).
The last nonleaf node is
(n-2)/2
(integer division).
You can verify these observations using the tree (
n
= 12) shown in Figure
9-6
.
•
0
37
1
2
43
25
3
5
4
6
79
73
69
84
11
10
7
8
9
32
18
65
56
48
Figure 9-6.
A binary tree stored in an array starting at 0
You are urged to rewrite
heapSort
so that it sorts the array
num[0..n-1]
. As a hint, note that the only change
required in
siftDown
is in the calculation of
bigger
. Instead of
2 * root
, we now use
2 * root + 1
.
9.2 Building a Heap Using siftUp
Consider the problem of adding a new node to an existing heap. Specifically, suppose
num[1]
to
num[n]
contain a
heap. We want to add a new number,
newKey
, so that
num[1]
to
num[n+1]
contain a heap that includes
newKey
. We
assume the array has room for the new key.
For example, suppose we have the heap shown in Figure
9-7
and we want to add
40
to the heap. When the new
number is added, the heap will contain 13 elements. We imagine
40
is placed in
num[13]
(but do not store it there,
as yet) and compare it with its parent
43
in
num[6]
. Since
40
is smaller, the heap property is satisfied; we place
40
in
num[13]
, and the process ends.
Search WWH ::
Custom Search