Java Reference
In-Depth Information
1
37
2
3
43
25
4
5
6
7
65
73
48
84
11
12
9
8
10
32
18
79
56
69
Figure 9-1.
A binary tree view of the array
Suppose we now require that the value at each node be greater than or equal to the values in its left and right
subtrees, if present. As it is, only node 6 and the leaves have this property. Shortly, we will see how to rearrange the
nodes so that
all
nodes satisfy this condition. But, first, we give such a structure a name:
A
heap
is an almost complete binary tree such that the value at the root is greater than or equal to
the values at the left and right children, and the left and right subtrees are also heaps.
An immediate consequence of this definition is that the largest value is at the root. Such a heap is referred to as
a
max-heap
. We define a
min-heap
with the word
greater
replaced by
smaller
. In a min-heap, the
smallest
value is at
the root.
Let's now convert the binary tree in Figure
9-1
into a max-heap.
9.1.1 Converting a Binary Tree into a Max-Heap
First, we observe that all the leaves are heaps since they have no children.
Starting at the last nonleaf node (6, in the example), we convert the tree rooted there into a max-heap. If the value
at the node is greater than its children, there is nothing to do. This is the case with node 6, since 84 is bigger than 32.
Next, we move on to node 5. The value here, 48, is smaller than at least one child (both, in this case, 56 and 69). We
first find the larger child (69) and interchange it with node 5. Thus, 69 ends up in node 5, and 48 ends up in node 11.
Next, we go to node 4. The larger child, 79, is moved to node 4, and 65 is moved to node 9. At this stage, the tree
looks like that in Figure
9-2
.
1
37
2
3
43
25
4
6
5
7
79
73
69
84
12
11
8
9
10
18
65
56
48
32
Figure 9-2.
The tree after nodes 6, 5, and 4 have been processed
Search WWH ::
Custom Search