Java Reference
In-Depth Information
1
84
2
3
73
79
4
5
6
7
65
37
69
43
12
11
13
9
8
10
32
18
25
56
48
Figure 9-7.
A heap to which we will add a new item
But suppose we want to add
80
to the heap. We imagine
80
is placed in
num[13]
(but do not actually store it there,
as yet) and compare it with its parent
43
in
num[6]
. Since
80
is bigger, we move
43
to
num[13]
and imagine
80
being
placed in
num[6]
.
Next, we compare
80
with its parent
73
in
num[3]
. It is bigger, so we move
73
to
num[6]
and imagine
80
being
placed in
num[3]
.
We then compare
80
with its parent
84
in
num[1]
. It is smaller, so we place
80
in
num[3]
, and the process ends.
Note that if we were adding
90
to the heap,
84
would be moved to
num[3]
, and
90
would be inserted in
num[1]
.
It is now the largest number in the heap.
Figure
9-8
shows the heap after
80
is added.
1
84
2
3
79
80
4
5
6
7
65
37
69
73
11
12
13
43
9
8
10
18
25
56
48
32
Figure 9-8.
The heap after 80 is added
The following code adds
newKey
to a heap stored in
num[1]
to
num[n]
:
child = n + 1;
parent = child / 2;
while (parent > 0) {
if (newKey <= num[parent]) break;
num[child] = num[parent]; //move down parent
child = parent;
parent = child / 2;
}
num[child] = newKey;
n = n + 1;
Search WWH ::
Custom Search