Java Reference
In-Depth Information
FIGURE 26-8
The steps in creating a heap of the entries 20, 40, 30, 10, 90, and
70 by using
reheap
(a) An array of entries
(b) The complete tree that
the array represents
40
23
30
20
20
10
45
90
70
6
0
1
40
30
10
90
70
(c) After
reheap(3)
(d) After
reheap(2)
20
20
40
70
90
70
10
90
30
40
30
10
(e) During
reheap(1)
(f) After
reheap(1)
90
90
20
70
40
70
40
30
20
30
10
10
By the observation at the end of Segment 26.11,
reheap
is O(
h
i
), where
h
i
is the height of the
subtree rooted at index
i
. In the worst case, the heap would be a full tree of height
h
. Each node in
level
l
<
h
is the root of a subtree whose height is
h
-
l
+
1. Moreover, level
l
contains 2
l
- 1
nodes.
Thus, the sum of the heights of the subtrees rooted at level
l
of a full heap is (
h
-
l
+
1)
×
2
l
- 1
.
Since the loop in the previous segment ignores the nodes in the last level—level
h
—of the
heap, its complexity is
§
·
h
-
¦
1
2
l
-
1
¨
¸
(
hl
-
+
1
)
⋅
O
¨
¸
©
l
=
1
¹
Exercise 6 at the end of this chapter asks you to show that this expression is equivalent to O(2
h
),
which is O(
n
).
Note:
You can create a heap more efficiently by using the method
reheap
instead of the
method
add
.
