Java Reference
In-Depth Information
FIGURE 26-7
The steps in adding 20, 40, 30, 10, 90, and 70 to an initially
empty heap
20
20
40
40
40
20
30
20
40
40
40
20
30
20
30
90
30
10
90
10
20
10
90
90
90
40
70
40
30
40
30
20
30
10
20
10
20
70
10
26.14
Using
reheap
.
A more efficient way to create a heap uses the method
reheap
. We begin by placing
the entries for the heap into an array beginning at index 1. Figure 26-8a provides an example of one
such array. This array can represent the complete tree shown in Figure 26-8b. Does this tree contain
any semiheaps that we can transform into heaps? The leaves are semiheaps, but they are also heaps.
Thus, we can ignore the entries 70, 90, and 10. These entries are at the end of the array.
Moving toward the beginning of the array, we encounter 30, which is the root of a semiheap
within the tree pictured in Figure 26-8b. If we apply
reheap
to this semiheap, we get the tree in
Figure 26-8c. Continuing in this manner, we apply
reheap
to the semiheap rooted at 40 and then to
the one rooted at 20. Parts
d
,
e
, and
f
of Figure 26-8 show the results of these steps. Figure 26-8f is
the desired heap.
The following Java statements transform the array
heap
—whose entries are at the indices 1
through
lastIndex
—into a heap:
for
(
int
rootIndex = lastIndex / 2; rootIndex > 0; rootIndex--)
reheap(rootIndex);
In applying
reheap
, we begin at the first nonleaf closest to the end of the array. This nonleaf is at
index
lastIndex/2
, since it is the parent of the last leaf in the tree. We then work toward
heap[1]
.
Question 8
If an array represents a heap, and
lastIndex
is the index of the heap's last leaf,
show why the index of the first nonleaf closest to the end of the array is
lastIndex/2
.
26.15
Using
reheap
to transform an array of entries into a heap takes less work than if we used
add
to add
the entries to the heap. In fact, building a heap in this manner is O(
n
), as we will now demonstrate.
