Java Reference
In-Depth Information
figure 21.18
(a) After
percolateDown(6)
;
(b) after
percolateDown(5)
92
92
47
21
47
21
20
12
25
63
20
12
25
63
61
17
55
37
45
64
83
73
61
17
55
37
45
64
83
73
(a)
(b)
figure 21.19
(a) After
percolateDown(4)
;
(b) after
percolateDown(3)
92
92
47
21
47
21
17
12
25
63
17
12
25
63
61
20
55
37
45
64
83
73
61
20
55
37
45
64
83
73
(a)
(b)
figure 21.20
(a) After
percolateDown(2)
;
(b) after
percolateDown(1)
and
buildHeap
terminates
92
12
12
21
17
21
17
37
25
63
20
37
25
63
61
20
55
47
45
64
83
73
61
92
55
47
45
64
83
73
(a)
(b)
To bound the running time of
buildHeap
, we must bound the number of
dashed lines. We can do so by computing the sum of the heights of all the
nodes in the heap, which is the maximum number of dashed lines. We
expect a small number because half the nodes are leaves and have height 0
and a quarter of the nodes have height 1. Thus only a quarter of the nodes
(those not already counted in the first two cases) can contribute more than
1 unit of height. In particular, only one node contributes the maximum
height of
⎣
log
N
⎦
.
The linear-time
bound can be
shown by comput-
ing the sum of the
heights of all the
nodes in the heap.
Search WWH ::
Custom Search