Java Reference
In-Depth Information
1
7
2
3
4
6
4
5
6
7
1
2
3
5
(A)
1
7
2
3
5
6
4
5
6
7
4
2
1
3
(B)
Figure5.20
Two series of exchanges to build a max-heap. (a) This heap is built
by a series of nine exchanges in the order (4-2), (4-1), (2-1), (5-2), (5-4), (6-3),
(6-5), (7-5), (7-6). (b) This heap is built by a series of four exchanges in the order
(5-2), (7-3), (7-1), (6-1).
Each call to
insert
takes (log n) time in the worst case, because the value
being inserted can move at most the distance from the bottom of the tree to the top
of the tree. Thus, to insert n values into the heap, if we insert them one at a time,
will take (n log n) time in the worst case.
If all n values are available at the beginning of the building process, we can
build the heap faster than just inserting the values into the heap one by one. Con-
sider Figure 5.20(a), which shows one series of exchanges that could be used to
build the heap. All exchanges are between a node and one of its children. The heap
is formed as a result of this exchange process. The array for the right-hand tree of
Figure 5.20(a) would appear as follows:
7
4
6
1
2
3
5
Figure 5.20(b) shows an alternate series of exchanges that also forms a heap,
but much more efficiently. The equivalent array representation would be
7
5
6
4
2
1
3
From this example, it is clear that the heap for any given set of numbers is not
unique, and we see that some rearrangements of the input values require fewer ex-
changes than others to build the heap. So, how do we pick the best rearrangement?
