Java Reference
In-Depth Information
744
2. Move the value of the last node of the heap into the root node, and remove the
last node. Now the heap property may be violated for the root node, because
one or both of its children may be smaller.
3. Promote the smaller child of the root node. (See
Figure 19
continued.) Now the
root node again fulfills the heap property. Repeat this process with the demoted
child. That is, promote the smaller of its children. Continue until the demoted
child has no smaller children. The heap property is now fulfilled again. This
process is called Ȓfixing the heapȓ.
Inserting and removing heap elements is very efficient. The reason lies in the
balanced shape of a heap. The insertion and removal operations visit at most h nodes,
where h is the height of the tree. A heap of height h contains at least 2
hɨ1
elements,
but less than 2
h
elements. In other words, if n is the number of elements, then
744
745
2
h ɨ 1
2
h
ʎ n <
or
h ɨ 1 ʎ
log
2
( n) < h
This argument shows that the insertion and removal operations in a heap with n
elements take O(log(n)) steps.
Inserting or removing a heap element is an O(log(n)) operation.
Contrast this finding with the situation of binary search trees. When a binary search
tree is unbalanced, it can degenerate into a linked list, so that in the worst case
insertion and removal are O(n) operations.
The regular layout of a heap makes it possible to store heap nodes efficiently in an
array.
Heaps have another major advantage. Because of the regular layout of the heap nodes,
it is easy to store the node values in an array. First store the first layer, then the
second, and so on (see
Figure 20
). For convenience, we leave the 0 element of the
