Java Reference
In-Depth Information
leaf at the rightmost position of the last level of the tree. By doing so, we may,
however, violate the heap property of Eq. 8.1, so that we need to transform
this tree into a heap by swapping child-parent keys until we again get a heap.
For example, consider adding element 25 to the heap. Figure 8.3 depicts the
three stages:
-
(1) add node 25 at the first place available on the last level of the tree,
-
(2) swap that node with parent element 17 (since 25
>
17),
-
(3) swap again with parent element 22, and reach the final heap status since
35
<
37.
37
37
37
Ok
22
31
22
31
25
31
17
16
25
16
2 3
2 3
16
22
2 3
9 25
9
17
17
12
6
12
6
9
17
17
12
6
Not a heap anymore! 25
>
17
Not a heap anymore! 25
>
22
It is a heap: 25
<
37
Figure 8.3
Adding element 25 to the heap: First, add a new node at the first
immediate empty position; then eventually swap this node with its parent until
the heap property is recovered
These basic step operations translate into corresponding operations on the
array implicitly encoding the heap as follows:
Program 8.4
Adding an element to the heap
static void
addHeap(
int
element , Heap h)
h.
label
[h. size]=element;
h . s i z e ++;
int
i=h. size ;
int
j=i /2;
while
(i
>
1&&h.
label
[i]
>
h.
label
[j])
{
int
tmp=h .
label
[i];
h.
label
[i]=h.
label
[j];
h.
label
[j]=tmp;
i=j ;
// swap
j=i /2;
}
}
Search WWH ::
Custom Search